Pattern Guide
Gray Code & Bit Tricks
"Adjacent Gray codes differ by one bit. Bit tricks: lowbit, popcount, bit pairs."
Gray code is a binary encoding where consecutive numbers differ by exactly one bit. Encode: G(n) = n XOR (n>>1). Decode: iterate from MSB. Applications: error correction, puzzles, circular navigation. This article also covers advanced bit manipulation: isolate/clear lowest set bit, iterate over subsets of a bitmask, count set bits (popcount), and power-of-two tricks.
Problems you can solve with this pattern
4 problems · click any to start solving
// Gray code
const toGray = n => n ^ (n >> 1);
const fromGray = g => {
let n = 0;
for (; g; g >>= 1) n ^= g;
return n;
};
// Bit tricks
const lowbit = n => n & (-n); // lowest set bit
const clearLow = n => n & (n - 1); // clear lowest set bit
const popcount = n => { let c=0; while(n){n&=n-1;c++;} return c; }; // count set bits
const isPow2 = n => n > 0 && !(n & (n-1));
const log2 = n => 31 - Math.clz32(n); // floor(log2(n)) for n > 0
// Iterate all subsets of a bitmask (including empty)
function forEachSubset(mask, callback) {
for (let s = mask; s > 0; s = (s - 1) & mask) callback(s);
callback(0); // empty subset
}
// Total subsets of mask with k bits: C(popcount(mask), k)
// Sum over all subsets: 2^popcount(mask) subsets total
// Enumerate all bitmasks of n bits with exactly k bits set (Gosper's hack)
function nextCombination(mask) {
const c = mask & (-mask);
const r = mask + c;
return (((r ^ mask) >> 2) / c) | r;
}Gray code tricks: (1) Encode n: G = n ^ (n>>1), (2) Decode G: n=0, then iterate MSB to LSB, each bit = previous XOR current. Bit tricks: n & (n-1) clears lowest set bit, n & (-n) isolates lowest set bit (lowbit), popcount = count set bits (32-bit: use Brian Kernighan). Iterating over subsets of a mask: for(let s = mask; s > 0; s = (s-1) & mask) — visits all non-empty subsets.
// Gray code
const toGray = n => n ^ (n >> 1);
const fromGray = g => {
let n = 0;
for (; g; g >>= 1) n ^= g;
return n;
};
// Bit tricks
const lowbit = n => n & (-n); // lowest set bit
const clearLow = n => n & (n - 1); // clear lowest set bit
const popcount = n => { let c=0; while(n){n&=n-1;c++;} return c; }; // count set bits
const isPow2 = n => n > 0 && !(n & (n-1));
const log2 = n => 31 - Math.clz32(n); // floor(log2(n)) for n > 0
// Iterate all subsets of a bitmask (including empty)
function forEachSubset(mask, callback) {
for (let s = mask; s > 0; s = (s - 1) & mask) callback(s);
callback(0); // empty subset
}
// Total subsets of mask with k bits: C(popcount(mask), k)
// Sum over all subsets: 2^popcount(mask) subsets total
// Enumerate all bitmasks of n bits with exactly k bits set (Gosper's hack)
function nextCombination(mask) {
const c = mask & (-mask);
const r = mask + c;
return (((r ^ mask) >> 2) / c) | r;
}- n & (n-1): clear lowest set bit (use to count set bits in O(k))
- n & (-n): isolate lowest set bit (lowbit, used in Fenwick tree)
- n ^ (n>>1): encode Gray code
- (s-1) & mask: iterate over subsets of mask
- Gosper's hack: next bitmask with same popcount
Subset iteration trick: for(let s = mask; s > 0; s = (s-1) & mask) visits all 2^popcount(mask) - 1 non-empty subsets. Time: O(2^popcount) per mask, O(3^n) over all masks (each element: in neither, only outer, or in sub).