Pattern Guide
Bit Counting & Manipulation Tricks
"Count set bits, Hamming distance, Brian Kernighan's trick, DP counting bits."
Bit counting problems count set bits (1s) in numbers or ranges, compute Hamming distances, or use bit properties for optimization. Key tricks: n & (n-1) clears the lowest set bit (Brian Kernighan's), n & (-n) isolates the lowest set bit, x ^ (x-1) creates a mask of lowest bit and all below. DP for counting bits in [0..n]: dp[i] = dp[i >> 1] + (i & 1).
Problems you can solve with this pattern
4 problems · click any to start solving
// Count set bits using Brian Kernighan's algorithm
function countBits(n) {
let count = 0;
while (n) { n &= n - 1; count++; } // clear lowest set bit each iteration
return count;
}
// Count bits for all numbers 0..n using DP
function countBitsDP(n) {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
dp[i] = dp[i >> 1] + (i & 1); // dp[i] = dp[i/2] + last_bit
return dp;
}
// Isolate lowest set bit
const lowestBit = n => n & (-n); // e.g., 6 (110) → 2 (010)
// Check if power of 2
const isPow2 = n => n > 0 && (n & (n-1)) === 0;
// Hamming distance between x and y
const hammingDist = (x, y) => countBits(x ^ y);Brian Kernighan: n & (n-1) removes the lowest set bit. Count set bits by repeated application until n=0. DP counting bits: for i in [1..n], dp[i] = dp[i>>1] + (i&1). Lowest set bit: n & (-n). Check power of 2: n & (n-1) == 0. XOR trick: a ^ a = 0, so XOR of array with duplicates cancels pairs, leaving the single element.
// Count set bits using Brian Kernighan's algorithm
function countBits(n) {
let count = 0;
while (n) { n &= n - 1; count++; } // clear lowest set bit each iteration
return count;
}
// Count bits for all numbers 0..n using DP
function countBitsDP(n) {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
dp[i] = dp[i >> 1] + (i & 1); // dp[i] = dp[i/2] + last_bit
return dp;
}
// Isolate lowest set bit
const lowestBit = n => n & (-n); // e.g., 6 (110) → 2 (010)
// Check if power of 2
const isPow2 = n => n > 0 && (n & (n-1)) === 0;
// Hamming distance between x and y
const hammingDist = (x, y) => countBits(x ^ y);-
n & (n-1) — clear lowest set bit (Brian Kernighan, count bits in O(k))-
n & (-n) — isolate lowest set bit (used in Fenwick tree)-
n & (n-1) == 0 — power of 2 check-
a ^ a = 0 — XOR cancellation (find single element)-
dp[i] = dp[i>>1] + (i&1) — count bits for all 0..n in O(n)Hamming distance at scale: For n numbers across 32 bits, O(32n) instead of O(n²) pairwise. For each bit: contribution = (count of 1s) × (count of 0s).