在Lua中使用32位位运算比较64位有符号数字

2016-2-19 15:53:53
收藏：0
阅读：85
评论：2

我正在Redis上使用Lua，并想比较两个有符号64位数字，它们存储在两个8字节/字符字符串中。

如何使用Redis中可用的库来比较它们？ http://redis.io/commands/EVAL#available-libraries

我想知道 >/< 和 == 检查。我认为这可能涉及为每个64位整数提取两个32位数字，并对这些数字进行一些聪明的数学计算，但我不确定。

我有一些代码可以让这个问题更具体化。 a0，a1，b0，b1都是用于表示两个64位有符号整数的msb和lsb的32位数字：

-- ...
local comp_int64s = function (a0, a1, b0, b1)
    local cmpres = 0
    -- TOOD: Real comparison
    return cmpres
end
local l, a0, a1, b0, b1
a0, l = bit.tobit(struct.unpack("I4", ARGV[1]))
a1, l = bit.tobit(struct.unpack("I4", ARGV[1], 5))
b0, l = bit.tobit(struct.unpack("I4", blob))
b1, l = bit.tobit(struct.unpack("I4", blob, 5))
print("Cmp result", comp_int64s(a0, a1, b0, b1))

编辑：添加了代码

点赞
用户2546626
用户2546626

比较是一个简单的字符串比较s1 == s2。

大于是当 s1 != s2 且 i1 < i2 的情况。

小于就需要真正的工作了。string.byte可以将单个字节作为unsigned char获取。对于无符号整数，您只需要从下往上检查字节：如果b1==b2 -> 检查下一个字节；检查所有字节 -> false(相等)；b1>b2 -> false(大于)；b1<b2 -> true。有符号的需要更多步骤：首先检查符号位（最高字节 >127）。如果设置了符号 1 但没有设置符号 2，则整数 1 为负数但整数 2 不是 -> true。相反的情况显然会导致false。当两个符号相同时，您可以执行无符号处理。

当您可以将更多字节打包到整数中时，这也很好，但您必须调整符号位检查。如果您有LuaJIT，您可以使用ffi库将字符串转换为字节数组到int64中。

2016-02-18 21:37:58
用户557406
用户557406

我想到了一个方法，看起来是可以工作的。但是有点丑陋。

第一步是将前32位作为2的补码进行比较 #’s MSB符号位保持不变，因此数字保持正确的关系

-1  —> -1
0 —> 0
9223372036854775807 = 0x7fff ffff ffff ffff -> 0x7ffff ffff = 2147483647

因此，从MSB返回结果可以工作，除非它们相等，然后需要检查LSB。

我有几种情况来建立一些模式：

-1 = 0xffff ffff ffff ffff
-2 = 0xffff ffff ffff fefe
32位是：
-1 -> 0xffff ffff = -1
-2 -> 0xffff fffe = -2
-1 > -2 就像 -1 > -2 : GOOD

和

8589934591 = 0x0000 0001 ffff ffff
8589934590 = 0x0000 0001 ffff fefe
32位是：
8589934591 -> ffff ffff = -1
8589934590 -> ffff fffe = -2
8589934591 > 8589934590 就像 -1 > -2 : GOOD

MSB上的符号位无关紧要，因为负数之间和正数之间有相同的关系。 例如，不考虑符号位，lsb值为 0xff > 0xfe，总是成立的。

如果低32位的MSB不同怎么办？

0xff7f ffff 7fff ffff = -36,028,799,166,447,617
0xff7f ffff ffff ffff = -36,028,797,018,963,969
32位是：
-..799.. -> 0x7fff ffff = 2147483647
-..797.. -> 0xffff ffff = -1
-..799.. < -..797.. 就像 2147483647 < -1 : BAD!

因此，我们需要忽略低32位的符号位。由于不考虑符号位时LSB的关系相同，因此仅使用最低的32位无符号即可适用于所有情况。

这意味着我想要MSB为有符号值，而LSB为无符号值 - 所以将 I4 更改为 i 4 以获得LSB。同时，正式地使用大端并在 struct.unpack 的调用中使用 '>' ：

-- ...
local comp_int64s = function (as0, au1, bs0, bu1)
    if as0 > bs0 then
        return 1
    elseif as0 < bs0 then
        return -1
    else
        -- msb's equal comparing lsbs - these are unsigned
        if au1 > bu1 then
            return 1
        elseif au1 < bu1 then
            return -1
        else
            return 0
        end
    end
end
local l, as0, au1, bs0, bu1
as0, l = bit.tobit(struct.unpack(">i4", ARGV[1]))
au1, l = bit.tobit(struct.unpack(">I4", ARGV[1], 5))
bs0, l = bit.tobit(struct.unpack(">i4", blob))
bu1, l = bit.tobit(struct.unpack(">I4", blob, 5))
print("Cmp result", comp_int64s(as0, au1, bs0, bu1))
2016-02-18 22:58:12

作者:

用户557406

用户557406
推荐文章