Bitwise Operators

lua-users home
wiki

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. However, there are Lua libraries for this as well as some patched versions of Lua.

Implementations of bitwise operators in Lua:

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

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 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:

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;
assuming i is right aligned and all bits to the left of the field are zero; this is the case in the patch above where this would be nice (where sextp is the optional argument indicating that sign extension is desired):
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):

Typical uses include

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.


RecentChanges · preferences
edit · history
Last edited July 16, 2013 4:15 am GMT (diff)