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

Answer 2

If you read through the function in the following link you will see that if you have an array of each octal digit, and the binary representation, then use the gsub function to replace each digit in the octal representation with the binary one.

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

For gsub you may want to look at http://lua-users.org/wiki/StringLibraryTutorial

Once you have that, loop through each character and see if they differ and mark to chsnge that position.

Answer 3

I think the best way would be to do this:

1. check the rightmost bit, i.e. check if both numbers are even or odd. If one is and the other is not, this bit is different, so add 1 to the weight sum.
2. Shift 1 bit to the right (either using bit32.rshift(number, 1) or by taking integer result of division by 2).
3. If number is 0, you're done otherwise repeat at 1.

Answer 4

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