Bit Utils

lua-users home
wiki

These are bitwise operations implemented entirely in Lua.

XOR

-- Bitwise XOR - thanks to Reuben Thomas
local floor = math.floor
function bxor (a,b)
  local r = 0
  for i = 0, 31 do
    local x = a / 2 + b / 2
    if x ~= floor (x) then
      r = r + 2^i
    end
    a = floor (a / 2)
    b = floor (b / 2)
  end
  return r
end

If you need speed, the following is a lot faster (Arno Wagner <arno@wagner.name>):

function bin_xor(x, y)
   local z = 0
   for i = 0, 31 do
      if (x % 2 == 0) then                      -- x had a '0' in bit i
         if ( y % 2 == 1) then                  -- y had a '1' in bit i
            y = y - 1 
            z = z + 2 ^ i                       -- set bit i of z to '1' 
         end
      else                                      -- x had a '1' in bit i
         x = x - 1
         if (y % 2 == 0) then                  -- y had a '0' in bit i
            z = z + 2 ^ i                       -- set bit i of z to '1' 
         else
            y = y - 1 
         end
      end
      y = y / 2
      x = x / 2
   end
   return z
end

It is also possible to do this without using the power function. The below implementation should be faster than the above in most cases. Though admittedly I have not verified this experimentally.

function xor(a,b)
   pow = 1
   c = 0
   while a > 0 or b > 0 do
      c = c + (XOR_l[(a % 2)+1][(b % 2)+1] * pow)
      a = math.floor(a/2)
      b = math.floor(b/2)
      pow = pow * 2
   end
   return c
end

XOR_l =
{ 
   {0,1},
   {1,0},
}

If speed is not your concern, the following could be shorter.

local function nand(x,y,z)
    z=z or 2^16
    if z<2 then
        return 1-x*y
    else
        return nand((x-x%z)/z,(y-y%z)/z,math.sqrt(z))*z+nand(x%z,y%z,math.sqrt(z))
    end
end
math["not"]=function(y,z)
    return nand(nand(0,0,z),y,z)
end
math["and"]=function(x,y,z)
    return nand(math["not"](0,z),nand(x,y,z),z)
end
math["or"]=function(x,y,z)
    return nand(math["not"](x,z),math["not"](y,z),z)
end
math["xor"]=function(x,y,z)
    return math["and"](nand(x,y,z),math["or"](x,y,z),z)
end

Flags

function testflag(set, flag)
  return set % (2*flag) >= flag
end

function setflag(set, flag)
  if set % (2*flag) >= flag then
    return set
  end
  return set + flag
end

function clrflag(set, flag) -- clear flag
  if set % (2*flag) >= flag then
    return set - flag
  end
  return set
end


-- Test suite
b = {
  ['_0000'] = 0, ['_0001'] = 1, ['_0010'] = 2, ['_0011'] = 3,
  ['_1000'] = 8, ['_1010'] = 10, ['_1011'] = 11,
}
assert(not testflag(b._0000, b._0001))
assert(not testflag(b._0000, b._0010))
assert(not testflag(b._0010, b._0001))
assert(    testflag(b._0010, b._0010))
assert(setflag(b._0000, b._0001) == b._0001)
assert(setflag(b._0000, b._0010) == b._0010)
assert(setflag(b._1010, b._0001) == b._1011)
assert(setflag(b._1010, b._0010) == b._1010)
assert(clrflag(b._0000, b._0001) == b._0000)
assert(clrflag(b._0000, b._0010) == b._0000)
assert(clrflag(b._1010, b._0001) == b._1010)
assert(clrflag(b._1010, b._0010) == b._1000)

See Also


RecentChanges · preferences
edit · history
Last edited September 25, 2013 5:30 am GMT (diff)