counting the difference in bits when comparing two numbers in Lua

Question

I would like to compare two numbers to determine the number of bits which must be flipped in order make them equal.

For instance, 5 and 6 would require 2 bit flips.

I can do this manually, but would like to write a Lua function to do it for me such as:

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

I'm only interested in comparing octals to octals (heheh), so the function would return a value 0-3. Is there an efficient/elegant way to do this that would be better than using a table?

Answer 1

The bit32 library introduced in Lua 5.2 makes this process rather simple.

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

However, if you're only comparing numbers in a small enough range, such as that of 0 to 7, you could simply precompute and save the results.

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