Bitwise Operators

wiki

!Lua
 bit.tobit(x)          -- normalize number to the numeric range of
                       -- bit operations (all bit ops use this implicitly)
 bit.tohex(x[,n])      -- convert x to hex with n digits (default 8)
 bit.bnot(x)           -- bitwise not of x
 bit.band(x1[,x2...])  -- bitwise and of x1, x2, ...
 bit.bor(x1[,x2...])   -- bitwise or of x1, x2, ...
 bit.bxor(x1[,x2...])  -- bitwise xor of x1, x2, ...
 bit.lshift(x, n)      -- left-shift of x by n bits
 bit.rshift(x, n)      -- logical right-shift of x by n bits
 bit.arshift(x, n)     -- arithmetic right-shift of x by n bits
 bit.rol(x, n)         -- left-rotate of x by n bits
 bit.ror(x, n)         -- right-rotate of x by n bits
 bit.bswap(x)          -- byte-swap of x (little-endian <-> big-endian)
 

!Lua
 bit.bits           -- number of bits usable in bitwise operations
 bit.bnot(a)        -- returns the one's complement of a
 bit.band(w1, ...)  -- returns the bitwise and of the w's
 bit.bor(w1, ...)   -- returns the bitwise or of the w's
 bit.bxor(w1, ...)  -- returns the bitwise exclusive or of the w's
 bit.lshift(a, b)   -- returns a shifted left b places
 bit.rshift(a, b)   -- returns a shifted logically right b places
 bit.arshift(a, b)  -- returns a shifted arithmetically right b places
 bit.cast(a)        -- cast a to the internally-used integer type
 

!Lua
 bits.create(value, number)     -- return bitmap of given size set to value
 bits:set(value)                -- set all bits to value, return bitmap
 bits:set(value, n1[,n2[n3,...]]) -- set these bits to value, return bitmap
 bits:get(n)                    -- get value of this bit
 bits:get(n1[,n2[n3,...]])      -- get value of these bits
 bits:iterator()                -- return iterator for all bits => i,v
 bits:iterator(n)               -- return iterator starting at bit n => i,v
 bits:iterator(n1, n2)          -- return iterator over range [n1..n2] => i,v
 bits:index(value)              -- return iterator => next index with the value
 bits:index(value, start)       -- return index of next bit with the value
 bits:isequal(b)  bits == b     -- return true or false for equality
 bits:notbits()   - bits        -- return NOT of the bitmap
 bits:orbits(b)   bits + b      -- return OR of the bitmaps
 bits:andbits(b)  bits * b      -- return AND of the bitmaps
 bits:xorbits(b)  bits % b      -- return XOR of the bitmaps
 bits:orbits(n1, n2[, n3,...])  -- return OR of these bits
 bits:andbits(n1, n2[, n3,...]) -- return AND of these bits
 bits:xorbits(n1, n2[, n3,...]) -- return XOR of these bits
 bits:copy()                    -- return a copy of the bitmap
 bits:printlimit()              -- return current limit
 bits:printlimit(n|"all"|"*")   -- set n or all bits printed, return new limit
 bits:size(), #bits             -- return the bit capacity
 bits:ones()                    -- return the number of 1 bits
 bits.version()                 -- return the version of module
 

!Lua
 function bit(p)
   return 2 ^ (p - 1)  -- 1-based indexing
 end
 
 -- Typical call:  if hasbit(x, bit(3)) then ...
 function hasbit(x, p)
   return x % (p + p) >= p       
 end
 
 function setbit(x, p)
   return hasbit(x, p) and x or x + p
 end
 
 function clearbit(x, p)
   return hasbit(x, p) and x - p or x
 end
 

!Lua
 bit.bnot(n) -- bitwise not (~n)
 bit.band(m, n) -- bitwise and (m & n)
 bit.bor(m, n) -- bitwise or (m | n)
 bit.bxor(m, n) -- bitwise xor (m ^ n)
 bit.brshift(n, bits) -- right shift (n >> bits)
 bit.blshift(n, bits) -- left shift (n << bits)
 bit.blogic_rshift(n, bits) -- logic right shift(zero fill >>>)
 

!Lua
 Hex2Bin(s)
 Bin2Hex(s)
 Hex2Dec(s)
 Dec2Hex(s)
 Bin2Dec(s)
 Dec2Bin(s [, num])
 BMAnd(v, m)
 BMNAnd(v, m)
 BMOr(v, m)
 BMXOr(v, m)
 BMNot(v, m) 
 

 Infix bitwise operators for AND (&, __and), OR (|, __or), XOR (^^, __xor).
 Infix bitwise operators for SHIFT LEFT (<<, __shl) and SHIFT RIGHT (>>, __shr).
 Unary bitwise negation operator (~, __not).
 Infix arithmetic operator for INTEGER DIVISION (\, __intdiv).
     accepts both ~= and != for comparison. 
 

 x&y                __bit_and
 x|y                __bit_or
 x^^y               __bit_xor
 ~x                 __bit_not
 -- also has arithmetic shifts:
 x<<y              __bit_lshift
 x>>y              __bit_rshift
 

 | & ^^ << >> ~ \\ !=
 

!Lua
 -- example
 local a1= enum.new( 0x10, "I'm A" )
 assert( tonumber(a1)==16 )
 assert( tostring(a1)=="0x10" )
 assert( tonumber(a1"not")==4294967279 )
 assert( tostring(a1"not")=="0xffffffef" )
 local c1= enum.new( 10 )   -- I'm None!
 assert( c1[3] == 1 )  -- 10 == 0x1010: bit 3 _is_ set
 

sext = 1 << (len - 1); i = (i ^ sext) - sext;

if (len < LI_BITS)
 { i &= LI_MASK(len);
   if (sextp) 
   { lua_Integer sext = 1 << (len - 1);
     i = (i ^ sext) - sext;
   }
 }
 

 bit.tobit(x)          -- normalize number to the numeric range of
                       -- bit operations (all bit ops use this implicitly)
 bit.tohex(x[,n])      -- convert x to hex with n digits (default 8)
 bit.bnot(x)           -- bitwise not of x
 bit.band(x1[,x2...])  -- bitwise and of x1, x2, ...
 bit.bor(x1[,x2...])   -- bitwise or of x1, x2, ...
 bit.bxor(x1[,x2...])  -- bitwise xor of x1, x2, ...
 bit.lshift(x, n)      -- left-shift of x by n bits
 bit.rshift(x, n)      -- logical right-shift of x by n bits
 bit.arshift(x, n)     -- arithmetic right-shift of x by n bits
 bit.rol(x, n)         -- left-rotate of x by n bits
 bit.ror(x, n)         -- right-rotate of x by n bits
 bit.bswap(x)          -- byte-swap of x (little-endian <-> big-endian)
 

 bit.bits           -- number of bits usable in bitwise operations
 bit.bnot(a)        -- returns the one's complement of a
 bit.band(w1, ...)  -- returns the bitwise and of the w's
 bit.bor(w1, ...)   -- returns the bitwise or of the w's
 bit.bxor(w1, ...)  -- returns the bitwise exclusive or of the w's
 bit.lshift(a, b)   -- returns a shifted left b places
 bit.rshift(a, b)   -- returns a shifted logically right b places
 bit.arshift(a, b)  -- returns a shifted arithmetically right b places
 bit.cast(a)        -- cast a to the internally-used integer type
 

 bits.create(value, number)     -- return bitmap of given size set to value
 bits:set(value)                -- set all bits to value, return bitmap
 bits:set(value, n1[,n2[n3,...]]) -- set these bits to value, return bitmap
 bits:get(n)                    -- get value of this bit
 bits:get(n1[,n2[n3,...]])      -- get value of these bits
 bits:iterator()                -- return iterator for all bits => i,v
 bits:iterator(n)               -- return iterator starting at bit n => i,v
 bits:iterator(n1, n2)          -- return iterator over range [n1..n2] => i,v
 bits:index(value)              -- return iterator => next index with the value
 bits:index(value, start)       -- return index of next bit with the value
 bits:isequal(b)  bits == b     -- return true or false for equality
 bits:notbits()   - bits        -- return NOT of the bitmap
 bits:orbits(b)   bits + b      -- return OR of the bitmaps
 bits:andbits(b)  bits * b      -- return AND of the bitmaps
 bits:xorbits(b)  bits % b      -- return XOR of the bitmaps
 bits:orbits(n1, n2[, n3,...])  -- return OR of these bits
 bits:andbits(n1, n2[, n3,...]) -- return AND of these bits
 bits:xorbits(n1, n2[, n3,...]) -- return XOR of these bits
 bits:copy()                    -- return a copy of the bitmap
 bits:printlimit()              -- return current limit
 bits:printlimit(n|"all"|"*")   -- set n or all bits printed, return new limit
 bits:size(), #bits             -- return the bit capacity
 bits:ones()                    -- return the number of 1 bits
 bits.version()                 -- return the version of module
 

 function bit(p)
   return 2 ^ (p - 1)  -- 1-based indexing
 end
 
 -- Typical call:  if hasbit(x, bit(3)) then ...
 function hasbit(x, p)
   return x % (p + p) >= p       
 end
 
 function setbit(x, p)
   return hasbit(x, p) and x or x + p
 end
 
 function clearbit(x, p)
   return hasbit(x, p) and x - p or x
 end
 

 bit.bnot(n) -- bitwise not (~n)
 bit.band(m, n) -- bitwise and (m & n)
 bit.bor(m, n) -- bitwise or (m | n)
 bit.bxor(m, n) -- bitwise xor (m ^ n)
 bit.brshift(n, bits) -- right shift (n >> bits)
 bit.blshift(n, bits) -- left shift (n << bits)
 bit.blogic_rshift(n, bits) -- logic right shift(zero fill >>>)
 

 Hex2Bin(s)
 Bin2Hex(s)
 Hex2Dec(s)
 Dec2Hex(s)
 Bin2Dec(s)
 Dec2Bin(s [, num])
 BMAnd(v, m)
 BMNAnd(v, m)
 BMOr(v, m)
 BMXOr(v, m)
 BMNot(v, m) 
 

 Infix bitwise operators for AND (&, __and), OR (|, __or), XOR (^^, __xor).
 Infix bitwise operators for SHIFT LEFT (<<, __shl) and SHIFT RIGHT (>>, __shr).
 Unary bitwise negation operator (~, __not).
 Infix arithmetic operator for INTEGER DIVISION (\, __intdiv).
     accepts both ~= and != for comparison. 
 

 x&y                __bit_and
 x|y                __bit_or
 x^^y               __bit_xor
 ~x                 __bit_not
 -- also has arithmetic shifts:
 x<<y              __bit_lshift
 x>>y              __bit_rshift
 

 | & ^^ << >> ~ \\ !=
 

 -- example
 local a1= enum.new( 0x10, "I'm A" )
 assert( tonumber(a1)==16 )
 assert( tostring(a1)=="0x10" )
 assert( tonumber(a1"not")==4294967279 )
 assert( tostring(a1"not")=="0xffffffef" )
 local c1= enum.new( 10 )   -- I'm None!
 assert( c1[3] == 1 )  -- 10 == 0x1010: bit 3 _is_ set
 

sext = 1 << (len - 1); i = (i ^ sext) - sext;

if (len < LI_BITS)
 { i &= LI_MASK(len);
   if (sextp) 
   { lua_Integer sext = 1 << (len - 1);
     i = (i ^ sext) - sext;
   }
 }
 

As of version 5.2, Lua ships with the library [bit32] that adds support for bitwise operations. Previous versions of Lua did not include bitwise operators, but bit32 has been backported to version 5.1. Alternatively, there are Lua libraries for this as well as some patched versions of Lua.

Implementations of bitwise operators in Lua:

• C Library implementations:
  • [Lua BitOp] (5.1) - C library providing bitwise operations on fixed-sized bitfields implemented as Lua numbers. Has consistent semantics across 16, 32 and 64 bit platforms as well as IEEE 754 doubles, int32_t and int64_t lua_Number types. Also defines LuaJIT 2 bit op semantics. Generally regarded as current best-practice for bit ops in Lua. Similar interface to bitlib but newer and intended to supersede it [2][3].
  • [bitlib] (5.0/5.1) - original C library providing bitwise operations on fixed-size bitfields implemented as Lua numbers.
  • http://staff.science.uva.nl/~hansm/publications.html adt.bits module in lua-modules.zip (Hans van der Meer) - implements arbitrary length bitfields as userdata in C.
  • [nixio.bit] - drop-in replacement for bitlib, included with nixio
• Pure Lua implementations:
  • [Iterating bits in Lua] (5.1) - bitwise test/set/clear operations - blogged by RiciLake
  • [LuaBit] (5.1)
  • [BinDecHex.lua] - (5.0/5.1) implementations of bitwise operations and binary<->decimal<->hexadecimal conversion.
  • BitUtils - some bitwise operators implementations on the wiki.
  • LuaList:2002-09/msg00134.html (4.0) (post by RobertoIerusalimschy)
  • [bit.numberlua] (used by ModuleCompressDeflateLua). Pure Lua number-based implementations of bitwise operators. Provides interfaces similar to Lua 5.2 "bit32" and LuaJit BitOp "bit". bxor implementation is similar to Roberto's. (DavidManura)
• Lua patch implementations (extended compiler syntax and VM opcodes):
  • Bitwise operators in LuaPowerPatches (5.1) - patch for bitwise operators
  • RiscLua - a variant of Lua patched with bitwise operators
  • hextype.patch - LuaList:2006-11/msg00430.html (5.1) - patch supporting new hex type (different from Lua_Number) with bitwise operators
  • Enum/bit operations in LuaPowerPatches (5.1) - 32-bit bitfields, supporting overloaded [] and () ops.

Lua BitOp (release 1.0.1) Description

bit.tobit(x)          -- normalize number to the numeric range of
                      -- bit operations (all bit ops use this implicitly)
bit.tohex(x[,n])      -- convert x to hex with n digits (default 8)
bit.bnot(x)           -- bitwise not of x
bit.band(x1[,x2...])  -- bitwise and of x1, x2, ...
bit.bor(x1[,x2...])   -- bitwise or of x1, x2, ...
bit.bxor(x1[,x2...])  -- bitwise xor of x1, x2, ...
bit.lshift(x, n)      -- left-shift of x by n bits
bit.rshift(x, n)      -- logical right-shift of x by n bits
bit.arshift(x, n)     -- arithmetic right-shift of x by n bits
bit.rol(x, n)         -- left-rotate of x by n bits
bit.ror(x, n)         -- right-rotate of x by n bits
bit.bswap(x)          -- byte-swap of x (little-endian <-> big-endian)

bitlib (release 25) Description

bit.bits           -- number of bits usable in bitwise operations
bit.bnot(a)        -- returns the one's complement of a
bit.band(w1, ...)  -- returns the bitwise and of the w's
bit.bor(w1, ...)   -- returns the bitwise or of the w's
bit.bxor(w1, ...)  -- returns the bitwise exclusive or of the w's
bit.lshift(a, b)   -- returns a shifted left b places
bit.rshift(a, b)   -- returns a shifted logically right b places
bit.arshift(a, b)  -- returns a shifted arithmetically right b places
bit.cast(a)        -- cast a to the internally-used integer type

bitlib is implemented in C. Internally, each bit array is implemented as an integer type. MIT licensed.

adt.bits (2009-04)

bits.create(value, number)     -- return bitmap of given size set to value
bits:set(value)                -- set all bits to value, return bitmap
bits:set(value, n1[,n2[n3,...]]) -- set these bits to value, return bitmap
bits:get(n)                    -- get value of this bit
bits:get(n1[,n2[n3,...]])      -- get value of these bits
bits:iterator()                -- return iterator for all bits => i,v
bits:iterator(n)               -- return iterator starting at bit n => i,v
bits:iterator(n1, n2)          -- return iterator over range [n1..n2] => i,v
bits:index(value)              -- return iterator => next index with the value
bits:index(value, start)       -- return index of next bit with the value
bits:isequal(b)  bits == b     -- return true or false for equality
bits:notbits()   - bits        -- return NOT of the bitmap
bits:orbits(b)   bits + b      -- return OR of the bitmaps
bits:andbits(b)  bits * b      -- return AND of the bitmaps
bits:xorbits(b)  bits % b      -- return XOR of the bitmaps
bits:orbits(n1, n2[, n3,...])  -- return OR of these bits
bits:andbits(n1, n2[, n3,...]) -- return AND of these bits
bits:xorbits(n1, n2[, n3,...]) -- return XOR of these bits
bits:copy()                    -- return a copy of the bitmap
bits:printlimit()              -- return current limit
bits:printlimit(n|"all"|"*")   -- set n or all bits printed, return new limit
bits:size(), #bits             -- return the bit capacity
bits:ones()                    -- return the number of 1 bits
bits.version()                 -- return the version of module

Iterating bits in Lua Description

function bit(p)
  return 2 ^ (p - 1)  -- 1-based indexing
end

-- Typical call:  if hasbit(x, bit(3)) then ...
function hasbit(x, p)
  return x % (p + p) >= p       
end

function setbit(x, p)
  return hasbit(x, p) and x or x + p
end

function clearbit(x, p)
  return hasbit(x, p) and x - p or x
end

• [Iterating bits in Lua] - some pure Lua 5.1 bitwise operations blogged by RiciLake

This is more of a design pattern than an actual library. It is implemented in Lua. Internally, each bit array is implemented as a Lua number. The primitive operations above provide simple code to test/set/clear bits in a number. Bitwise operations can be defined in terms of these functions.

LuaBit (release 0.4) Description

bit.bnot(n) -- bitwise not (~n)
bit.band(m, n) -- bitwise and (m & n)
bit.bor(m, n) -- bitwise or (m | n)
bit.bxor(m, n) -- bitwise xor (m ^ n)
bit.brshift(n, bits) -- right shift (n >> bits)
bit.blshift(n, bits) -- left shift (n << bits)
bit.blogic_rshift(n, bits) -- logic right shift(zero fill >>>)

LuaBit is implemented entirely in Lua. Internally, each bit array is implemented as a Lua number or a Lua array of digits. This package also includes functions for converting numbers to/from hex strings, a 'utf8' module for UTF8 -> UCS2 string conversion, and a 'noki' module related to Nokia PCs. MIT licensed.

BinDecHex (2007-10) Description

Hex2Bin(s)
Bin2Hex(s)
Hex2Dec(s)
Dec2Hex(s)
Bin2Dec(s)
Dec2Bin(s [, num])
BMAnd(v, m)
BMNAnd(v, m)
BMOr(v, m)
BMXOr(v, m)
BMNot(v, m) 

BinDecHex is written entirely in Lua. Internally, each bit array is implemented as a Lua string in Big-endian form. BSD licensed.

BitUtils Description

BitUtils provides a few assorted code snippets implemented entirely in Lua. Internally, in general, each bit array is implemented as a Lua number.

Bitwise Operators Power Patch Description

Infix bitwise operators for AND (&, __and), OR (|, __or), XOR (^^, __xor).
Infix bitwise operators for SHIFT LEFT (<<, __shl) and SHIFT RIGHT (>>, __shr).
Unary bitwise negation operator (~, __not).
Infix arithmetic operator for INTEGER DIVISION (\, __intdiv).
    accepts both ~= and != for comparison. 

This is implemented as a patch to Lua. Internally, each bit array is implemented as a Lua number. Operators are provided as syntax extensions and as VM opcodes (including metamethods).

RiscLua Description

RiscLua, versions previous to version 6, uses hex literals and has bitwise operators, each with a corresponding event:

x&y                __bit_and
x|y                __bit_or
x^^y               __bit_xor
~x                 __bit_not
-- also has arithmetic shifts:
x<<y              __bit_lshift
x>>y              __bit_rshift

This is implemented as a patch to Lua. Internally, each bit array is implemented as a Lua number. Operators are provided as syntax extensions and as VM opcodes (including metamethods). The patch is not standalone but rather incorporated into RiscLua.

hextype.patch Description

| & ^^ << >> ~ \\ !=

This is implemented as a patch to Lua. Internally, each bit array is implemented as a new primitive value type (type(x) == 'hex', LUA_THEX) different from 'number'. This type is itself internally an unsigned integer. Operators are provided as syntax extensions and as VM opcodes (including metamethods).

Enum/bit operations in LuaPowerPatches Description

-- example
local a1= enum.new( 0x10, "I'm A" )
assert( tonumber(a1)==16 )
assert( tostring(a1)=="0x10" )
assert( tonumber(a1"not")==4294967279 )
assert( tostring(a1"not")=="0xffffffef" )
local c1= enum.new( 10 )   -- I'm None!
assert( c1[3] == 1 )  -- 10 == 0x1010: bit 3 _is_ set

This is implemented as a patch to Lua. Internally, each bit array is implemented as a new primitive value type (type() returns two values: "enum" and the enum family name). enum values have overloaded [] and () operations for performing bit-wise operations on the Lua side.

Plea

The implementations above deal differently (or not at all in some cases) with two issues:

• how is the sign treated in right shifts?
• how are results converted back to Lua numbers (especially with respect to the sign of the result)

One of the implementations assumes a 32 bit integer and provides signed and unsigned right shifts.

Another uses long long and unsigned long long and depends on the C compiler to perform right shifts correctly in each case (it happens to work great for me on x86 with gcc, but C89 and C99 don't specify how signed right shifts are performed; it is "implementation-defined behavior").

A third seems to completely ignore the issue and gives us whatever the C compiler decides to do with lua_Integers.

Note that when adding operators, Java defines the >> operator to use sign extension and the >>> operator to use zero extension.

None of them seem to provide a way to portably convert an arbitrary sized bit field to a signed number.

[This] patch would be great if bitfield took another optional boolean argument to indicate that the result should be sign extended to the full size of a lua_Integer.

BTW, a branch free way to sign extend a bitfield (Henry S. Warren Jr., CACM v20 n6 June 1977) is this:

sext = 1 << (len - 1); i = (i ^ sext) - sext;

if (len < LI_BITS)
{ i &= LI_MASK(len);
  if (sextp) 
  { lua_Integer sext = 1 << (len - 1);
    i = (i ^ sext) - sext;
  }
}

Purpose

There are at least two very different reasons for bitwise operations: (1) set operations on a small universe of members and (2) manipulation of fields in explicit representations of data defined externally to the Lua program. The referenced implementations of bitwise operators are designed primarily for the latter. For an implementation of the former, see Asko's Enum/bit operations patch in LuaPowerPatches.

Examples

Here's a sampling of Lua code that utilizes bitwise operators (use cases):

• BaseSixtyFour
• ModuleCompressDeflateLua (deflate/gzip/zlib)
• SerialCommunication
• [MD5 in Lua (4.x)]
• [Metalua's Lua opcode functions (lopcodes.lua)]
• [scite-st lexers]
• [packet.lua in nmaps]
• Examples contained in the [Lua BitOp] distribution: MD5 and nsievebits (bit vectors).
• HammingWeight (bit and bit32)

Typical uses include

• reading/writing/encoding/decoding binary structures (files, protocols, encodings, compressions) in Lua -- see StructurePacking
• calling C API functions that take bit flags (typically OR-ed) or structures -- including Alien
• algorithms more efficiently expressed in terms of bit vectors

Comments

For a language intended to be interfaced to C/C++, it's strange that bitwise operators are not part of the syntax. Sure, they can be implemented as functions -- but this is clumsy. See FeatureProposals.

"How can bitwise operations be performed?" is a LuaFaq question.

Note: hex literals were added in Lua 5.1: 0xfe.

Java has an abstraction of bit vectors called EnumSet [1]. Something similar might be done on Lua.