论坛 › 算法交流 › 问大家一个比较大小的问题

无心人 发表于 2008-3-31 17:21:19

CPU的进位逻辑是怎么写的？

无心人 发表于 2008-3-31 20:53:14

假设能比较高低各32位数字

大于返回FFFFFFFF 不大于返回00000000
等于返回FFFFFFFF 不等于返回00000000
则先进行大于比较
再进行等于比较
两个结果相减
得到9种结果是互不相等的9个64位数字
问题是如何区别他们呢

shines 发表于 2008-4-8 07:40:10

看到个文章，不过感觉还是太复杂了

x< y:   (x-y) ^ ((x^y) & ((x-y)^x))
x<=y:    (x|~y) & ((x^y) | ~(y-x))
x< y:   (~x&y) | ((~x|y) & (x-y))   // 无符号x,y比较
x<=y:    (~x|y) & ((x^y) | ~(y-x))   // 无符号x,y比较

无心人 发表于 2008-4-8 07:55:58

哦
楼上的方法什么地方转来的？

可以利用哦

无心人 发表于 2008-4-8 08:43:00

x< y:   (~x&y) | ((~x|y) & (x-y))

    mm0 = y
    mm1 = x

    movq mm2, mm1
    psubq mm1, mm0
    pcmpeqd mm3, mm3
    pxor mm3,mm2 //mm3=~x
    pandn mm2, mm0 //mm2=(~x & y)
    por mm3, mm0//mm3=(~x | y)
    pand mm3, mm1
    por mm2, mm3
8条指令得到x < y结果

shines 发表于 2008-4-8 09:27:02

http://www.yuanma.org/data/2007/1212/article_2922.htm

刚才看李开复的贴子不小心看到的，这文章亮点就上面那些，
刚才由于发帖数量限制贴不上来。

楼主代码写得很快啊，不管此方法效率如何，至少也提供了一种解决方案。

无心人 发表于 2008-4-8 09:45:48

该死的SSE2没求反运算
只好用FFFFFFFFFFFFFFF xor x = ~x代替

shines 发表于 2008-4-8 10:07:24

试了一下，比较大小的结果直接要取计算结果的最高位即可，
64bit运算即取bit63(假设bit0是最低位)，还算方便

liangbch 发表于 2008-4-8 11:38:58

我比较关心 64bit 无符号数的大小比较。

若a，b同为64bit无符号数。
old_a= a;
a=a+b;
if (a<old_a)
则一定有进位，否则没有进位。
所以a+b是否有进位转化为，64bit无符号数比较大小，现在的问题是:
a 和 old_a存储在 MMX 寄存器或者XMM寄存器,如何判定 a 是否小于 old_a.

无心人 发表于 2008-4-8 13:10:37

到这里
http://bbs.emath.ac.cn/thread-269-1-1.html
讨论加法问题吧

查看完整版本: 问大家一个比较大小的问题