Yet More Bit Hacks

September 3, 2013

I don’t like these bit hack exercises — my brain doesn’t seem to be wired that way — but I can tell from my statistics that lots of people do like them, so here’s another.

1. Compute the parity of a word, 1 if an odd number of bits is set, 0 if an even number of bits is set.

2. Reverse the bits in a word or byte.

3. Find the integer logarithm, base 2, of an integer data type.

Your task is to write programs to solve the three problems given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Yet More Bit Hacks”

  1. David said
    September 22, 2013 at 2:38 PM

    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 comment