posts - 4,  comments - 27,  trackbacks - 0
     今天偶然看到一个讲求较小值的帖子,让我突然想起一年前一次折腾逆向工程的尝试,当时用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>>31得到的是FFFFFFFF,再与上一个z,还是z,
    如果z > 0,  z>>31得到的是0000000,最终还是0
    所以最终的算法是
    z = x - y
    m = ((z >> 31) & z) + y;
    这个算法应该跟当初看到的比较接近了。它的优点很显然,全部是最基本的运算,而且不包含控制指令,而且完全可以直接由寄存器计算完成,效率很高。
   
    算法本身并非什么惊天地泣鬼神大算法,而且在编译器里肯定会有自己做这样的优化,其实最让我欣慰的是我这次的思路,思路非常清晰,很久没有动脑子的我,居然还能这么思考,我已经很高兴了。其中主要包含两种思想:分类讨论、降低元数(降二元为一元)。这也是使用非常广泛的方法了,前者主要帮助理清思路,后者主要降低复杂度。

Updated:
    之前用的是z>>32,用gcc编译会出现一个警告:
    right shift count >= width of type [enabled by default]
    但还不清楚会存在什么样的隐患,所以改成31
posted on 2011-08-22 23:58 夜风 阅读(14404) 评论(16)  编辑 收藏 引用 所属分类: 算法

FeedBack:
# re: min(x,y)高效算法
2011-08-23 09:33 | fuwutu
牛鼻哄哄的算法敢验证一下再发上来吗?
z = x - y
m = (z >> 32) & z + y;
C++里这m铁定赋为0了。  回复  更多评论
  
# re: min(x,y)高效算法
# re: min(x,y)高效算法
2011-08-23 11:20 | 哎哟,还要用户名
CMOVxx指令就可以了.  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 11:34 | 哎哟,还要用户名2
z>>31  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 19:21 | matrix42
如果z < 0,z>>32得到的是FFFFFFFF

有符号数右移有逻辑移位和算数移位两种阿,与编译器具体实现有关,你能保证移位结果就一定是FFFFFFFF啊???  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 19:47 | 夜风
@matrix42
既然是求差值,那z显然需要一个有符号的整型,对有符号整型右移,是算术移位  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 19:52 | 夜风
@fuwutu
不知道你的理由是什么?没有出现0的情况,不过少个括号倒是个问题,我忘记了&优先级低于+号,已经修正,谢谢关注  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 19:54 | 夜风
@哎哟,还要用户名2
效果一样,多一位少一位不影响  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 20:18 | 夜风
@哎哟,还要用户名2
z >> 32用gcc编译会有警告:
right shift count >= width of type [enabled by default]
虽然计算结果正确,但不知会有什么隐患,所以我已经改成31,谢谢关注  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-23 23:36 | dshe
@夜风
在C里面,移位偏移量大于等于类型宽度是undefined behavior。
另外有符号数如果值为负数的话右移是implementation-defined,不能保证是算术右移
  回复  更多评论
  
# re: min(x,y)高效算法[未登录]
2011-08-24 19:40 | a

既然已经有 ida 反汇编经验,至少对常用的汇编指令有个大概了解。
在x86下,最高效的求 两个整数的最大值‘、最小值的指令应该是:
cmp eax, ebx
cmovg/cmovl eax,ebx

再怎么高效的算法,在内嵌的机器指令面前都是浮云,


  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-24 22:42 | 夜风
@a
也许是我强调得不太清楚,我的写这文章的目的不在于向大家介绍算法本身,这些早已是成熟的算法,我只是从一个推理的角度,介绍我再现该算法的过程。结果不重要,实现也不重要,何必这么钻牛角尖呢?难道文章的中心思想就如此难以把握?  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-24 22:42 | 夜风
@a
也许是我强调得不太清楚,我的写这文章的目的不在于向大家介绍算法本身,这些早已是成熟的算法,我只是从一个推理的角度,介绍我再现该算法的过程。结果不重要,实现也不重要,何必这么钻牛角尖呢?难道文章的中心思想就如此难以把握?  回复  更多评论
  
# re: min(x,y)高效算法[未登录]
2011-08-25 17:01 | leo
在vc下测试,右移32位,就是本身值。记得书上说,有些编译器,在移位时,先对其取32的模。  回复  更多评论
  
# re: min(x,y)高效算法
2011-08-29 10:59 | TTEE
事实证明,这种算法效率最差,比if else慢50%以上。  回复  更多评论
  
# re: min(x,y)高效算法
2011-09-03 04:01 | 欲三更
@TTEE
那应该是编译器把if else方法优化了。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(1)

随笔分类(7)

随笔档案(4)

文章分类

最新评论

阅读排行榜

评论排行榜