min(x,y)高效算法

标签: min 算法 | 发表时间:2011-08-22 15:58 | 作者:夜风 Rooney
出处:http://www.cppblog.com/
     今天偶然看到一个讲求较小值的帖子,让我突然想起一年前一次折腾逆向工程的尝试,当时用IDA进行反汇编,看到一串汇编代码,非常精妙,最终发现仅仅是为了计算两个整数的较小值。可现在非常努力的回忆,就是想不起来是怎么做的。
     真的非常想再现那串算法,于是自己开始推敲。我来谈谈我推敲的过程。
     命题:给定整数x,y,计算较小值m。
     两个数的差异,在于他们的差,于是想到计算z = x - y,我想也许可以利用这个中间值,利用一些巧妙的位运算求出,可是貌似还是比较困难。于是我打算重新理一下思路:
可能出现的情况:(暂时忽略特殊情况 z = 0)
1. x < y
    z < 0
    就是要找到一个函数f,满足f(y , z) = x
2. x > y
    z > 0
    就需要这个f不仅满足1,而且满足此时f(y , z) = y

    因为算法的目的是使用加减法、位运算这些基本运算,尽可能简单的计算。所以我选择了加法运算
    y + g(z) = x , z = x - y < 0;
    y + g(z) = y , z = x - y > 0;
    最终变成寻求一元函数g
    就是
    g(z) = z, z < 0
    g(z) = 0, z > 0
    也就是要找到一个一元分段函数,而且需要运算简单,于是我想到了g(z) = (z >> 31) & z
    如果z < 0,z>>32得到的是FFFFFFFF,再与上一个z,还是z,
    如果z > 0,  z>>32得到的是0000000,最终还是0
    所以最终的算法是
    z = x - y
    m = ((z >> 31) & z) + y;
    这个算法应该跟当初看到的比较接近了。它的优点很显然,全部是最基本的运算,而且不包含控制指令,而且完全可以直接由寄存器计算完成,效率很高。
   
    算法本身并非什么惊天地泣鬼神大算法,而且在编译器里肯定会有自己做这样的优化,其实最让我欣慰的是我这次的思路,思路非常清晰,很久没有动脑子的我,居然还能这么思考,我已经很高兴了。其中主要包含两种思想:分类讨论、降低元数(降二元为一元)。这也是使用非常广泛的方法了,前者主要帮助理清思路,后者主要降低复杂度。

Updated:
    之前用的是z>>32,用gcc编译会出现一个警告:
    right shift count >= width of type [enabled by default]
    但还不清楚会存在什么样的隐患,所以改成31

夜风 2011-08-22 23:58 发表评论

相关 [min 算法] 推荐:

min(x,y)高效算法

- Rooney - C++博客-首页原创精华区
     今天偶然看到一个讲求较小值的帖子,让我突然想起一年前一次折腾逆向工程的尝试,当时用IDA进行反汇编,看到一串汇编代码,非常精妙,最终发现仅仅是为了计算两个整数的较小值. 可现在非常努力的回忆,就是想不起来是怎么做的.      真的非常想再现那串算法,于是自己开始推敲.      命题:给定整数x,y,计算较小值m.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

联接算法

- - CSDN博客数据库推荐文章
本文摘自《锋利的SQL》: http://item.jd.com/10380652.html. 在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划. 执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等.