|
今天偶然看到一个讲求较小值的帖子，让我突然想起一年前一次折腾逆向工程的尝试，当时用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 |