Yet More Bit Hacks

September 3, 2013

1. Counting parity: One approach counts the 1 bits, ignoring the 0 bits:

unsigned int v;
bool parity = false;

while (v)
{
  parity = !parity;
  v = v & (v - 1);
}

The other approach uses a byte-size table, here assembled with macros:

static const bool ParityTable256[256] =
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
    P6(0), P6(1), P6(1), P6(0)
};

The parity of a byte can be determined directly, the parity of a word can be determined in two ways:

unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];

or

unsigned char * p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];

If you only want to know the parity of a byte, and 64-bit arithmetic is available, you can distribute the byte’s bits through the available bits and compute the parity directly:

unsigned char b; // byte value to compute the parity of
bool parity =
  (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

I rather like that one.

2. Reversing bits: The obvious solution copies bits from the input to the output; remember from previous exercises that CHAR_BIT is the number of bits in a character (normally 8):

unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

You can use table lookup if you’re willing to set aside 256 bytes for the table:

static const unsigned char BitReverseTable256[256] =
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

As above, there are two solutions, one in integers and the other in characters:

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

c = (BitReverseTable256[v & 0xff] << 24) |
    (BitReverseTable256[(v >> 8) & 0xff] << 16) |
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

or

unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];

There is also a method of reversing the bits of a byte using 64-bit operations:

unsigned char b; // reverse this (8-bit) byte

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

3. Base-2 Logarithm: The base-2 logarithm of a 32-bit integer is the index of the highest set bit:

unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)

while (v >>= 1)
{
  r++;
}

Table lookup is an obvious alternative:

static const char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

As in the other two exercises, there are two possibilities:

unsigned int v; // 32-bit word to find the log of
unsigned r; // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

or

if (tt = v >> 24)
{
  r = 24 + LogTable256[tt];
}
else if (tt = v >> 16)
{
  r = 16 + LogTable256[tt];
}
else if (tt = v >> 8)
{
  r = 8 + LogTable256[tt];
}
else
{
  r = LogTable256[v];
}

You can see all these programs at work at http://programmingpraxis.codepad.org/mLbgPDHr.

Most of the solutions from the three exercises on bit hacks came from http://graphics.stanford.edu/~seander/bithacks.html.

About these ads

Pages: 1 2

One Response to “Yet More Bit Hacks”

  1. David said

    FORTH words to do this (64 bits)

    \ -- counting bits in 64 bit word --
    : bitcount ( n -- n )
        dup $5555555555555555 and  swap $AAAAAAAAAAAAAAAA and  1 rshift +
        dup $3333333333333333 and  swap $CCCCCCCCCCCCCCCC and  2 rshift +
        dup $0F0F0F0F0F0F0F0F and  swap $F0F0F0F0F0F0F0F0 and  4 rshift +
        dup $00FF00FF00FF00FF and  swap $FF00FF00FF00FF00 and  8 rshift +
        dup $0000FFFF0000FFFF and  swap $FFFF0000FFFF0000 and 16 rshift +
        dup $00000000FFFFFFFF and  swap $FFFFFFFF00000000 and 32 rshift + ;
    
    : parity ( n -- n )
        bitcount 1 and ;
    
    \ -- reverse bits in 64 bit word --
    : reversebits ( n -- n )
        dup  1 rshift $5555555555555555 and  swap $5555555555555555 and  1 lshift  or
        dup  2 rshift $3333333333333333 and  swap $3333333333333333 and  2 lshift  or
        dup  4 rshift $0F0F0F0F0F0F0F0F and  swap $0F0F0F0F0F0F0F0F and  4 lshift  or
        dup  8 rshift $00FF00FF00FF00FF and  swap $00FF00FF00FF00FF and  8 lshift  or
        dup 16 rshift $0000FFFF0000FFFF and  swap $0000FFFF0000FFFF and 16 lshift  or
        dup 32 rshift                        swap                       32 lshift  or ;
    
    \ log of unsigned integer (log -1 == 63), also lowbit (find lowest bit set)
    
    create convert64
        0 c,  1 c, 48 c,  2 c, 57 c, 49 c, 28 c,  3 c,
       61 c, 58 c, 50 c, 42 c, 38 c, 29 c, 17 c,  4 c,
       62 c, 55 c, 59 c, 36 c, 53 c, 51 c, 43 c, 22 c,
       45 c, 39 c, 33 c, 30 c, 24 c, 18 c, 12 c,  5 c,
       63 c, 47 c, 56 c, 27 c, 60 c, 41 c, 37 c, 16 c,
       54 c, 35 c, 52 c, 21 c, 44 c, 32 c, 23 c, 11 c,
       46 c, 26 c, 40 c, 15 c, 34 c, 20 c, 31 c, 10 c,
       25 c, 14 c, 19 c,  9 c, 13 c,  8 c,  7 c,  6 c,
    
    : (ulog)  ( n -- n )  \ use only when n is a power of two.
        $3F79D71B4CB0A89 * 58 rshift convert64 + c@ ;
    
    : lowbit  ( n -- n )
        dup negate and (ulog) ;
    
    : ulog   ( n -- n )
        dup 1  rshift or
        dup 2  rshift or
        dup 4  rshift or
        dup 8  rshift or
        dup 16 rshift or
        dup 32 rshift or
        dup 1 rshift - (ulog) ;
    

    Usage examples:

    1000 ulog . 9  ok
    9 parity . 0  ok
    254 parity . 1  ok
    hex  ok
    FFFF0000FFFF reversebits u. FFFF0000FFFF0000  ok
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: