Bitwise Operations

It's fairly convoluted though very efficient to encode lots of pieces of Boolean information into a single integer variable. Normal arithmetic and logical operations on such integer variables become unintuitive since we're not usually concerned with the value of the variables (e.g., 17) but rather with the status of individual bits (say, the first and fifth bits are set, all other bits are unset).

This page presents some bitwise operations I found useful while writing an extremely CPU-intensive ray-tracer. C syntax is used but the techniques can be applied to other languages including Java, often with only minor syntax changes.

Tests

Is a power of two:

v & (v-1) == 0
Has two or more set bits:

v & (v-1) > 0
Has exactly one set bit:

v && (v & (v-1) == 0) == true
Has all specified bits set:

v & bits == bits
Has at least one specified bit set:

v & bits > 0

Operations

Toggle specific bits:

v ^= b;
Set a bit:

v |= b;
Unset a bit:

v &= ~b;
Unset all bits apart from lowest set bit:

((v ^ (v-1)) + 1) >> 1
Unset the lowest set bit only:

v &= (v-1)

Other

Count number of set bits:

int n = 0; if (v) do { n++; } while (v &= (v-1)); return(n);
Compute log2 of a power of two:

float x=v; return (*(int*)&x >> 23) - 127;
Compute minimum of two signed 32-bit integers:

j + (((i-j) >> 31) & (i-j))