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.

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 616 other followers

%d bloggers like this: