lua - 在 Lua 中比较两个数字时计算位数的差异

Question

我想比较两个数字以确定必须翻转的位数才能使它们相等。

例如，5 和 6 需要 2 位翻转。

我可以手动执行此操作，但想编写一个 Lua 函数来为我执行此操作，例如：

function (a,b)
  return hammingweight of a xor b
end

我只对将八进制与八进制进行比较感兴趣（呵呵），因此该函数将返回值 0-3。有没有一种比使用桌子更好的有效/优雅的方法来做到这一点？

Answer 1

bit32Lua 5.2 中引入的库使这个过程变得相当简单。

local bxor, band, rshift = bit32.bxor, bit32.band, bit32.rshift
local function ham(a, b)
  a = bxor(a, b)
  b = 0 -- Reuse b to count one bits.
  while a > 0 do
    b = b + band(a, 1)
    a = rshift(a, 1)
  end
  return b
end

print(ham(5,6)) -- 2

但是，如果您只比较足够小的范围内的数字，例如0to 的数字7，您可以简单地预先计算并保存结果。

local bxor = bit32.bxor
local hamcache = {[0] = 0, 1, 1, 2, 1, 2, 2, 3}
local function ham(a, b)
  return hamcache[bxor(a, b)]
end

Answer 2

如果您阅读以下链接中的函数，您将看到如果您有一个包含每个八进制数字和二进制表示的数组，则使用 gsub 函数将八进制表示中的每个数字替换为二进制表示。

http://lua-users.org/lists/lua-l/2002-10/msg00244.html

对于 gsub，您可能需要查看http://lua-users.org/wiki/StringLibraryTutorial

一旦你有了它，循环遍历每个字符，看看它们是否不同并标记以改变那个位置。

Answer 3

local function octal_ham(a, b)
  local x = bit32.bxor(a, b)
  return x - math.floor(x/2) - math.floor(x/4)
end

Answer 4

我认为最好的方法是这样做：

1. 检查最右边的位，即检查两个数字是偶数还是奇数。如果一个是另一个不是，这个位是不同的，所以在权重和上加1。
2. 右移 1 位（使用bit32.rshift(number, 1)或取除以 2 的整数结果）。
3. 如果数字是 0，你就完成了，否则在 1 处重复。