Beautiful examples of bit manipulation

Question

What are the most elegant or useful examples of bit manipulation you have encountered or used?

Examples in all languages are welcome.

Answer 1

Classic XOR swap

Swap two variables using three XOR operations and no extra memory:

x ^= y
y ^= x
x ^= y

Great explanation on why this works

Of course on modern architectures and compilers this operation might actually be less efficient than a regular swap (for example, XCHG on x86), but this is still a very elegant operation, nonetheless.

Answer 2

This calculates the inverse square root of a float found in the Quake III engine :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

Pure genius..

Answer 3

Count number of 1 bits

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

(Updated B. Kernighan's version)

This beautiful manipulation counts how many 1 bits a certain value x has. By &ing x with x-1 the effect is that of removing the rightmost 1 bit in the value. Iterating this until none are left, and returning the number of iterations yields the number of 1 bits in x.

Answer 4

detect power-of-two-ness

if( !(x & (x-1)) ) printf("x is power-of-two");

EDIT d'oh, that's just almost the same as the "count number of 1-bits". However, here it is explicitly mentioned! Don't forget next time you need it.

Answer 5

Compute sum of two numbers

This one has no practical application whatsoever, but I find it cute all the same:

unsigned sum(unsigned a, unsigned b)
{
    if(a & b)
        return sum(a ^ b, (a & b) << 1);
    else
        return a ^ b;
}

Edit: Here's an explanation of how this works.

The idea is that XOR is already implements most of the sum operation, except for the carry. Here's a table to illustrate this:

a   b   a ^ b
0   0     0
0   1     1
1   0     1
1   1     0

On a single-bit level, this is exactly the same as summing the two bits. The only thing that is missing is the carry.

To implement the carry, we first need to identify the positions where we need to carry. These are those positions where both a and b have a bit set -- we identify these by taking a & b.

If there are no bits to carry, we're done -- simply return a ^ b.

If we do have carry bits, we want to add them to the next most significant bit -- hence the left shift. And how do we add them onto the intermediate result we got through the XOR? Simple, we just call ourselves recursively.

No practical value, but it's still kind of cute...

Answer 6

Count number of 1 bits, without looping

int bitcount(unsigned int n) {
   /* works for 32-bit numbers only    */

   register unsigned int tmp;

   tmp = n - ((n >> 1) & 033333333333)
           - ((n >> 2) & 011111111111);
   return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

(See http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/)

Answer 7

Multiply or divide a number per powers of 2 by shifiting left or right.

// x = 5 because it is being divided by 4 and shifting is 
// less expensive than division.
uint x = 20 >> 2; 

// y = 320, the same as 10 * 2 ^ 5
uint y = 10 << 5; 

Answer 8

One I created myself:

public static int split3i(int a) {
    // split out the lowest 10 bits to lowest 30 bits
    a=(a|(a<<12))&00014000377;
    a=(a|(a<<8)) &00014170017;
    a=(a|(a<<4)) &00303030303;
    a=(a|(a<<2)) &01111111111;
    return a;
}

This spreads out the bottom 10 bits of an integer, i.e.

00000000000000000000001111100111

becomes:

00001001001001001000000001001001

Why is this useful? Well it turns out this is critical to efficiently interleave a set of bits in order to implement the z-order transform in 3D.

Answer 9

Assuming that (x > y) evaluates to either 0 or 1 ...

value = (-(x > y)) & NUM;

is equivalent to ...

value = (x > y) ? NUM : 0

This can be tweaked to ....

value = ((-(x > y) & NUM) + X;

for its equvalent ...

value = (x > y) ? NUM + X : X;

Why? Sometimes (not often) it is useful to avoid branching and branch mispredictions. If your CPU and compiler supports conditional move instructions, it really is not that useful.

Answer 10

//  set (zo=1) or clear (zo=0) bits of m in x
#define conditional_set_bits(x,m,zo) ((x)^((-(zo)^(x))&(m)))

//  set r to x with n bits swapped at positions i and j
#define swap_bit_ranges(x,i,j,n,r) (r=(((x)>>i)^((x)>>j))&((1<<n)-1),r=(x)^((r<<i)|(r>>j)))

#define clear_least_significant_bit(x) ((x)&((x)-1))
#define clear_above_least_significant_bit(x) ((x)&-(x))

And everything here

Answer 11

int32 value;     
int32 sign = 1-(((Uint32)value>>30)&2); //sign val [1/-1]
value -= sign*factor;

This is a faster version (at least on my embedded processor) of

 if (value > 0) value -= factor;
 else           value += factor;

Answer 12

1) n Modulus of 2^x

Say, x = 3, so 2^x = 8

10 mod 8 = 2

mod = n & ( (1 << x) - 1 );

(1 << x) = 2^x
(1 << x) - 1 = 2^x - 1

2) Using Bits to Generate Subsets/ Disjoint Subsets/

I'm sorry, i don't have an example at the moment...

3) (x & 1) == 0 (x is even)

Answer 13

The most beautiful examples I've encountered are the ones I can understand in a snap. And I love the Erlang syntax for this.

Reading from the Erlang Programming Book, here is how you decode a TCP segment:

decode(<<SourcePort:16,
         DestinationPort:16,
         SequenceNumber:32,
         AckNumber::32,
         ...
       >>) ->
         ...

It's automatically binding the first 16 bits to the "SourcePort" variable, the next 16 bits to the "DestinationPort" one and so on...

It's startlingly high level, and I love it.

Answer 14

I like the way that, with an AND and an XOR, you can compute any bit value. Great fun for bitwise parallel programming:

(N*A)^X has the following truth table:

    X 0  1
    -------
A 0 | 0  1
A 1 | N ~N

For fun, I wrote an entire virtual machine, capable of addition, multiplication, etc., using only this logic and pattern-matched production rules.

I also recommend Knuth's TAOCP fascile 4 on bitwise programming.

Answer 15

An O(logN) bit-string reversal gave a "wow!"-moment to me. It was in a Dr. Dobb's journal that I saw it first.

Here's the routine for 32-bit integers. It can be extended to 64 bits and higher with proper choice of constants through divide-and-conquer.

unsigned int
reverse(register unsigned int x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));
}

(From The Aggregate Magic Algorithms. Sorry, I couldn't find the original Dr. Dobbs)