Bit Manipulation and Bitwise Operations
1. Bitmasking for Subset Enumeration
| Concept | Technique | Formula/Pattern | Use Case |
|---|---|---|---|
| Subset as Bitmask | Represent subset using binary number | bit i set → element i included |
Enumerate all 2n subsets |
| Iterate All Subsets | Loop from 0 to 2n-1 | for (let mask = 0; mask < (1<<n); mask++) |
Generate powerset efficiently |
| Check Bit Set | Test if bit i is set in mask | (mask >> i) & 1 or mask & (1<<i) |
Determine element membership |
| Set Bit | Turn on bit i | mask | (1 << i) |
Add element to subset |
| Clear Bit | Turn off bit i | mask & ~(1 << i) |
Remove element from subset |
| Toggle Bit | Flip bit i | mask ^ (1 << i) |
Add/remove element toggle |
Example: Generate All Subsets Using Bitmask
function subsetsUsingBitmask(nums) {
const n = nums.length;
const result = [];
// Iterate through all possible subsets (2^n)
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
// Check each bit position
for (let i = 0; i < n; i++) {
// If bit i is set, include nums[i]
if ((mask >> i) & 1) {
subset.push(nums[i]);
}
}
result.push(subset);
}
return result;
}
console.log(subsetsUsingBitmask([1, 2, 3]));
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
// Mask representation:
// 000 (0) → []
// 001 (1) → [1]
// 010 (2) → [2]
// 011 (3) → [1,2]
// 100 (4) → [3]
// 101 (5) → [1,3]
// 110 (6) → [2,3]
// 111 (7) → [1,2,3]
Note: Bitmask subset enumeration is memory efficient (O(1) space for mask) and allows fast subset operations using bitwise operators. Perfect for problems with n ≤ 20 elements.
2. Generate All Subsets Using Bits
| Operation | Bitwise Formula | Example | Application |
|---|---|---|---|
| Count Subsets | 2^n = 1 << n |
n=3 → 8 subsets | Total number of subsets |
| Iterate Submasks | for (s = mask; s; s = (s-1) & mask) |
Submasks of 101 → 101, 100, 001 | Enumerate all submasks of mask |
| Power of 2 Check | n & (n-1) === 0 |
8 (1000) & 7 (0111) = 0 | Detect exact power of 2 |
| Lowest Set Bit | n & -n |
12 (1100) → 4 (0100) | Extract rightmost 1-bit |
| Remove Lowest Bit | n & (n-1) |
12 (1100) → 8 (1000) | Clear rightmost 1-bit |
Example: Iterate All Submasks of a Mask
function iterateSubmasks(mask) {
const submasks = [];
// Standard submask iteration trick
for (let s = mask; s > 0; s = (s - 1) & mask) {
submasks.push(s);
}
// Don't forget empty submask (0)
submasks.push(0);
return submasks;
}
console.log(iterateSubmasks(5)); // 5 = 101 in binary
// Output: [5, 4, 1, 0]
// 101 → 100 → 001 → 000
// Why this works:
// mask = 101
// s-1 flips all bits from rightmost 1
// & mask keeps only bits that are in original mask
// 101 - 1 = 100, 100 & 101 = 100
// 100 - 1 = 011, 011 & 101 = 001
// 001 - 1 = 000, 000 & 101 = 000 (loop ends)Example: DP with Bitmask - Traveling Salesman Problem
function tsp(dist) {
const n = dist.length;
const VISITED_ALL = (1 << n) - 1;
const dp = Array(1 << n).fill(null).map(() => Array(n).fill(Infinity));
// Start from city 0
dp[1][0] = 0;
// Iterate all subsets
for (let mask = 1; mask <= VISITED_ALL; mask++) {
for (let last = 0; last < n; last++) {
// If last city not in mask, skip
if (!(mask & (1 << last))) continue;
// Previous mask without last city
const prevMask = mask ^ (1 << last);
// Try all previous cities
for (let prev = 0; prev < n; prev++) {
if (prevMask & (1 << prev)) {
dp[mask][last] = Math.min(
dp[mask][last],
dp[prevMask][prev] + dist[prev][last]
);
}
}
}
}
// Return to city 0 from any city
let minCost = Infinity;
for (let i = 1; i < n; i++) {
minCost = Math.min(minCost, dp[VISITED_ALL][i] + dist[i][0]);
}
return minCost;
}
const dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
];
console.log(tsp(dist)); // 803. Counting Set Bits (Brian Kernighan's Algorithm)
| Method | Algorithm | Time | Description |
|---|---|---|---|
| Brian Kernighan | n &= (n-1) in loop |
O(k) k=set bits |
Clears rightmost set bit each iteration |
| Naive Loop | Check each bit with >> |
O(log n) |
Loop through all 32/64 bits |
| Built-in | n.toString(2).split('1').length-1 |
O(log n) |
Convert to binary string and count '1's |
| Lookup Table | Precompute counts for 0-255 | O(1) |
Split number into bytes, lookup each |
| Parallel Count | SWAR (SIMD Within A Register) | O(1) |
Count bits in parallel using bit tricks |
Example: Brian Kernighan's Algorithm
function countSetBits(n) {
let count = 0;
// Each iteration removes rightmost set bit
while (n) {
n &= (n - 1);
count++;
}
return count;
}
console.log(countSetBits(13)); // 3 (1101 has 3 ones)
console.log(countSetBits(7)); // 3 (0111 has 3 ones)
// Trace for n=13 (1101):
// Iteration 1: 1101 & 1100 = 1100, count=1
// Iteration 2: 1100 & 1011 = 1000, count=2
// Iteration 3: 1000 & 0111 = 0000, count=3
// Why n & (n-1) removes rightmost set bit:
// n = ...10110100
// n-1 = ...10110011 (flips bits after rightmost 1)
// & = ...10110000 (rightmost 1 cleared)Example: Count Bits for All Numbers 0 to n (DP)
function countBits(n) {
const result = new Array(n + 1);
result[0] = 0;
for (let i = 1; i <= n; i++) {
// Key insight: count[i] = count[i >> 1] + (i & 1)
// Right shift removes last bit, &1 checks if last bit was 1
result[i] = result[i >> 1] + (i & 1);
}
return result;
}
console.log(countBits(5));
// [0, 1, 1, 2, 1, 2]
// 0: 0000 → 0 bits
// 1: 0001 → 1 bit
// 2: 0010 → 1 bit
// 3: 0011 → 2 bits
// 4: 0100 → 1 bit
// 5: 0101 → 2 bits
// Alternative DP: result[i] = result[i & (i-1)] + 1
// i & (i-1) removes rightmost set bit
function countBitsAlt(n) {
const result = new Array(n + 1);
result[0] = 0;
for (let i = 1; i <= n; i++) {
result[i] = result[i & (i - 1)] + 1;
}
return result;
}4. XOR Patterns (Single Number Problem)
| Property | Formula | Example | Application |
|---|---|---|---|
| Self XOR | a ^ a = 0 |
5 ^ 5 = 0 | Cancel out duplicates |
| XOR with 0 | a ^ 0 = a |
5 ^ 0 = 5 | Identity property |
| Commutative | a ^ b = b ^ a |
3 ^ 5 = 5 ^ 3 | Order doesn't matter |
| Associative | (a ^ b) ^ c = a ^ (b ^ c) |
Can group any way | Chain XOR operations |
| Find Unique | result = a1 ^ a2 ^ ... ^ an |
All pairs cancel | Find single non-duplicate |
| Swap Without Temp | a^=b; b^=a; a^=b |
Swap two variables | In-place swap |
Example: Single Number - Find Unique Element
function singleNumber(nums) {
let result = 0;
// XOR all numbers: duplicates cancel out
for (const num of nums) {
result ^= num;
}
return result;
}
console.log(singleNumber([4, 1, 2, 1, 2])); // 4
// 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2
// = 4 ^ (1 ^ 1) ^ (2 ^ 2)
// = 4 ^ 0 ^ 0
// = 4Example: Single Number II - Element Appears Thrice
function singleNumberII(nums) {
let ones = 0, twos = 0;
for (const num of nums) {
// Add to twos if already in ones
twos |= ones & num;
// XOR with ones
ones ^= num;
// Remove from both if appears 3 times
const threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
console.log(singleNumberII([2, 2, 3, 2])); // 3
// All numbers appear 3 times except one
// Alternative using bit counting
function singleNumberIIBitCount(nums) {
let result = 0;
// Count bits at each position
for (let i = 0; i < 32; i++) {
let sum = 0;
for (const num of nums) {
sum += (num >> i) & 1;
}
// If count not divisible by 3, unique number has this bit
if (sum % 3 !== 0) {
result |= (1 << i);
}
}
return result;
}Example: Single Number III - Two Unique Elements
function singleNumberIII(nums) {
// XOR all numbers: result = a ^ b (two unique numbers)
let xorAll = 0;
for (const num of nums) {
xorAll ^= num;
}
// Find rightmost set bit (where a and b differ)
const rightmostBit = xorAll & -xorAll;
// Partition into two groups based on this bit
let a = 0, b = 0;
for (const num of nums) {
if (num & rightmostBit) {
a ^= num;
} else {
b ^= num;
}
}
return [a, b];
}
console.log(singleNumberIII([1, 2, 1, 3, 2, 5])); // [3, 5]
// Step 1: 1^2^1^3^2^5 = 3^5 = 6 (110)
// Step 2: rightmost bit = 6 & -6 = 2 (010)
// Step 3: Partition by bit 1
// Group 1 (bit set): 2,3,2 → 3
// Group 2 (bit not set): 1,1,5 → 55. Bit Manipulation Tricks and Fast Operations
| Operation | Bit Trick | Equivalent | Use Case |
|---|---|---|---|
| Multiply by 2k | n << k |
n * (2^k) |
Fast multiplication by power of 2 |
| Divide by 2k | n >> k |
Math.floor(n / (2^k)) |
Fast division by power of 2 |
| Check Even/Odd | n & 1 |
n % 2 |
0=even, 1=odd |
| Modulo Power of 2 | n & (2^k - 1) |
n % (2^k) |
Fast modulo by power of 2 |
| Absolute Value | (n ^ (n >> 31)) - (n >> 31) |
Math.abs(n) |
Branchless absolute value |
| Min of Two | b ^ ((a ^ b) & -(a < b)) |
Math.min(a, b) |
Branchless minimum |
| Max of Two | a ^ ((a ^ b) & -(a < b)) |
Math.max(a, b) |
Branchless maximum |
| Sign Function | (n >> 31) | ((-n) >>> 31) |
-1 if n<0, 0 if n=0, 1 if n>0 | Get sign without branches |
| Next Power of 2 | Decrease by 1, set all bits right of MSB, add 1 | Find next 2k ≥ n | Round up to power of 2 |
| Isolate Rightmost 1 | n & -n |
Get lowest set bit | Extract least significant bit |
| Isolate Rightmost 0 | ~n & (n+1) |
Get lowest unset bit | Find first zero bit |
| Turn Off Rightmost 1 | n & (n-1) |
Clear lowest set bit | Remove least significant bit |
| Turn On Rightmost 0 | n | (n+1) |
Set lowest unset bit | Set first zero bit |
Example: Common Bit Tricks
// Check if power of 2
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}
// Get next power of 2
function nextPowerOfTwo(n) {
if (n <= 0) return 1;
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}
// Swap two numbers without temp variable
function swap(a, b) {
console.log(`Before: a=${a}, b=${b}`);
a ^= b;
b ^= a;
a ^= b;
console.log(`After: a=${a}, b=${b}`);
}
// Check if opposite signs
function oppositeSign(a, b) {
return (a ^ b) < 0;
}
console.log(isPowerOfTwo(16)); // true
console.log(nextPowerOfTwo(10)); // 16
swap(5, 10); // Before: a=5, b=10, After: a=10, b=5
console.log(oppositeSign(5, -3)); // true
console.log(oppositeSign(5, 3)); // falseExample: Fast Modulo and Multiplication
function fastOperations() {
const n = 25;
// Multiply by 8 (2^3)
console.log(n << 3); // 200 (same as n * 8)
// Divide by 4 (2^2)
console.log(n >> 2); // 6 (same as Math.floor(n / 4))
// Check even/odd
console.log(n & 1); // 1 (odd)
console.log(24 & 1); // 0 (even)
// Modulo 16 (2^4)
console.log(n & 15); // 9 (same as n % 16, where 15 = 16-1)
// Isolate rightmost set bit
console.log(12 & -12); // 4 (1100 → 0100)
// Remove rightmost set bit
console.log(12 & 11); // 8 (1100 → 1000)
}
fastOperations();
Note: While bit tricks are fast, modern compilers often optimize standard operations automatically. Use bit tricks for clarity and specific algorithms (like counting bits, XOR problems), not general arithmetic unless profiling shows benefit.
6. Hamming Distance (Bit Difference Count)
| Concept | Definition | Formula | Application |
|---|---|---|---|
| Hamming Distance | Number of positions where bits differ | countBits(x ^ y) |
Measure bit difference between numbers |
| XOR for Difference | XOR highlights different bits | x ^ y gives 1 where bits differ |
Find positions of difference |
| Total Hamming | Sum of all pairwise distances | Count contribution of each bit position | Analyze array bit differences |
| Hamming Weight | Number of 1-bits in number | countBits(n) |
Also called population count |
Example: Hamming Distance Between Two Numbers
function hammingDistance(x, y) {
// XOR to find differing bits, then count them
let xor = x ^ y;
let distance = 0;
// Brian Kernighan's algorithm
while (xor) {
xor &= (xor - 1);
distance++;
}
return distance;
}
console.log(hammingDistance(1, 4)); // 2
// 1 = 0001
// 4 = 0100
// XOR = 0101 (2 bits set)Example: Total Hamming Distance of Array
function totalHammingDistance(nums) {
let total = 0;
const n = nums.length;
// Check each bit position (0-31 for 32-bit integers)
for (let bit = 0; bit < 32; bit++) {
let countOnes = 0;
// Count how many numbers have this bit set
for (const num of nums) {
if ((num >> bit) & 1) {
countOnes++;
}
}
// Numbers with 1 * numbers with 0 = pairs with different bit
const countZeros = n - countOnes;
total += countOnes * countZeros;
}
return total;
}
console.log(totalHammingDistance([4, 14, 2])); // 6
// 4 = 0100
// 14 = 1110
// 2 = 0010
//
// Bit 0: [0,0,0] → 0*3 = 0
// Bit 1: [0,1,1] → 1*2 = 2
// Bit 2: [1,1,1] → 3*0 = 0
// Bit 3: [0,1,0] → 1*2 = 2
// Total = 0+2+0+2+2 = 67. Check Power of Two Using Bits
| Check | Technique | Why It Works | Edge Cases |
|---|---|---|---|
| Is Power of 2 | n > 0 && (n & (n-1)) === 0 |
Power of 2 has exactly one bit set | n=0 is NOT power of 2 |
| Count Check | countBits(n) === 1 |
Exactly one 1-bit present | Slower but more explicit |
| Is Power of 4 | (n & (n-1)) === 0 && (n & 0x55555555) |
Power of 2 with bit at even position | 0x55...5 = 01010101... pattern |
| Next Power of 2 | Set all bits right of MSB, then add 1 | Creates number like 2k-1, then +1 | Handle n ≤ 0 specially |
Example: Power of Two Variations
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}
function isPowerOfFour(n) {
// Must be power of 2 AND bit at even position (0,2,4,6,...)
// 0x55555555 = 01010101010101010101010101010101 (bits at even positions)
return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
}
function nextPowerOfTwo(n) {
if (n <= 1) return 1;
// Decrease by 1 to handle exact powers of 2
n--;
// Set all bits to the right of MSB
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Add 1 to get next power of 2
return n + 1;
}
console.log(isPowerOfTwo(16)); // true (10000)
console.log(isPowerOfTwo(18)); // false (10010)
console.log(isPowerOfFour(16)); // true (16 = 4^2)
console.log(isPowerOfFour(8)); // false (8 = 2^3, not 4^k)
console.log(nextPowerOfTwo(10)); // 16
console.log(nextPowerOfTwo(16)); // 16 (already power of 2)Example: Find Missing Power of Two
function missingPowerOfTwo(arr, n) {
// Array contains all powers of 2 from 2^0 to 2^n except one
// Use XOR to find missing
let xor = 0;
// XOR all elements in array
for (const num of arr) {
xor ^= num;
}
// XOR all powers of 2 from 0 to n
for (let i = 0; i <= n; i++) {
xor ^= (1 << i);
}
return xor; // Missing number
}
// Array has [1,2,8,16,32] - missing 4
console.log(missingPowerOfTwo([1, 2, 8, 16, 32], 5)); // 48. Gray Code Generation Algorithm
| Concept | Property | Formula | Use Case |
|---|---|---|---|
| Gray Code | Adjacent codes differ by exactly 1 bit | gray = binary ^ (binary >> 1) |
Error correction, rotary encoders |
| Binary to Gray | XOR with right-shifted version | g = b ^ (b >> 1) |
Convert standard binary to Gray |
| Gray to Binary | Accumulate XOR from MSB | b ^= g >> i for all i |
Decode Gray code to binary |
| N-bit Gray Codes | Recursive: reflect previous, prepend 0/1 | 2n unique codes | Generate all n-bit Gray codes |
Example: Generate Gray Code Sequence
function grayCode(n) {
const result = [];
const size = 1 << n; // 2^n
for (let i = 0; i < size; i++) {
// Convert binary i to Gray code
result.push(i ^ (i >> 1));
}
return result;
}
console.log(grayCode(2)); // [0, 1, 3, 2]
// Binary: 00, 01, 10, 11
// Gray: 00, 01, 11, 10
//
// 0 ^ (0 >> 1) = 0 ^ 0 = 0 (00)
// 1 ^ (1 >> 1) = 1 ^ 0 = 1 (01)
// 2 ^ (2 >> 1) = 2 ^ 1 = 3 (11)
// 3 ^ (3 >> 1) = 3 ^ 1 = 2 (10)
console.log(grayCode(3)); // [0,1,3,2,6,7,5,4]
// Verify: each adjacent pair differs by 1 bitExample: Gray Code Conversion
function binaryToGray(binary) {
return binary ^ (binary >> 1);
}
function grayToBinary(gray) {
let binary = gray;
// XOR with all right-shifted versions
while (gray >>= 1) {
binary ^= gray;
}
return binary;
}
// Alternative: recursive reflection method
function grayCodeRecursive(n) {
if (n === 0) return [0];
if (n === 1) return [0, 1];
// Get previous Gray codes
const prev = grayCodeRecursive(n - 1);
const result = [...prev];
// Reflect and prepend 1 (add 2^(n-1))
const prefix = 1 << (n - 1);
for (let i = prev.length - 1; i >= 0; i--) {
result.push(prefix | prev[i]);
}
return result;
}
console.log(binaryToGray(6)); // 5 (110 → 101)
console.log(grayToBinary(5)); // 6 (101 → 110)
console.log(grayCodeRecursive(3)); // [0,1,3,2,6,7,5,4]9. Gosper's Hack (Next Combination with Same Set Bits)
| Technique | Purpose | How It Works | Complexity |
|---|---|---|---|
| Gosper's Hack | Generate next k-combination in lexicographic order | Find next number with same bit count | O(1) per iteration |
| Pattern | Iterate all n choose k combinations | Maintains same number of set bits | Total: O(C(n,k)) |
| Formula | c = x & -x; r = x + c; x = (((r^x)>>2)/c)|r |
Finds next combination efficiently | Bitwise arithmetic only |
Example: Gosper's Hack - Enumerate k-Combinations
function gospersHack(n, k) {
const combinations = [];
// Start with k rightmost bits set: 2^k - 1
let set = (1 << k) - 1;
const limit = 1 << n;
while (set < limit) {
combinations.push(set);
// Gosper's hack: find next combination
const c = set & -set; // Rightmost set bit
const r = set + c; // Add to create carry
set = (((r ^ set) >> 2) / c) | r;
}
return combinations;
}
// Get all 3-bit combinations from 5 bits
console.log(gospersHack(5, 3));
// [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]
// Binary representations all have exactly 3 bits set:
// 00111 (7)
// 01011 (11)
// 01101 (13)
// 01110 (14)
// 10011 (19)
// ...
// Extract indices of set bits
function getIndices(mask) {
const indices = [];
let i = 0;
while (mask) {
if (mask & 1) indices.push(i);
mask >>= 1;
i++;
}
return indices;
}
const combs = gospersHack(5, 3);
console.log(combs.map(getIndices));
// [[0,1,2], [0,1,3], [0,2,3], [1,2,3], [0,1,4], ...]Example: Apply Gosper's Hack to Array
function generateCombinations(arr, k) {
const n = arr.length;
const result = [];
let set = (1 << k) - 1;
const limit = 1 << n;
while (set < limit) {
const combination = [];
// Extract elements based on set bits
for (let i = 0; i < n; i++) {
if ((set >> i) & 1) {
combination.push(arr[i]);
}
}
result.push(combination);
// Next combination
const c = set & -set;
const r = set + c;
set = (((r ^ set) >> 2) / c) | r;
}
return result;
}
console.log(generateCombinations(['a', 'b', 'c', 'd'], 2));
// [['a','b'], ['a','c'], ['b','c'], ['a','d'], ['b','d'], ['c','d']]1. Bitmasking for Subset Enumeration
| Operation | Technique | Steps | Complexity |
|---|---|---|---|
| Reverse Bits | Swap bits from outside to inside | Swap 16-bit halves, 8-bit, 4-bit, 2-bit, 1-bit | O(log n) bits |
| Swap Adjacent Bits | Mask odd and even bits separately | ((n & 0xAAAAAAAA)>>1)|((n & 0x55555555)<<1) |
O(1) |
| Swap Nibbles | Swap 4-bit groups | ((n & 0xF0F0F0F0)>>4)|((n & 0x0F0F0F0F)<<4) |
O(1) |
| Swap Bytes | Swap 8-bit groups | ((n & 0xFF00FF00)>>8)|((n & 0x00FF00FF)<<8) |
O(1) |
| Lookup Table | Precompute reverse for 0-255 | Split into bytes, lookup each, reassemble | O(1) |
Example: Reverse 32-bit Integer
function reverseBits(n) {
// Swap 16-bit halves
n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);
// Swap 8-bit halves within each 16-bit group
n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
// Swap 4-bit nibbles within each 8-bit group
n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
// Swap 2-bit pairs within each 4-bit group
n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
// Swap adjacent bits
n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
return n >>> 0; // Convert to unsigned
}
console.log(reverseBits(43261596).toString(2));
// Input: 00000010100101000001111010011100 (43261596)
// Output: 00111001011110000010100101000000 (964176192)Example: Bit Reversal Variants
// Simple bit-by-bit reversal
function reverseBitsSimple(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
result <<= 1;
result |= (n & 1);
n >>>= 1;
}
return result >>> 0;
}
// Swap adjacent bits
function swapAdjacentBits(n) {
// 0xAAAAAAAA = 10101010... (odd positions)
// 0x55555555 = 01010101... (even positions)
return (((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)) >>> 0;
}
// Swap nibbles (4-bit groups)
function swapNibbles(n) {
// 0xF0F0F0F0 = high nibbles, 0x0F0F0F0F = low nibbles
return (((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)) >>> 0;
}
// Reverse byte order (big-endian ↔ little-endian)
function reverseBytes(n) {
return (((n & 0xFF000000) >>> 24) |
((n & 0x00FF0000) >>> 8) |
((n & 0x0000FF00) << 8) |
((n & 0x000000FF) << 24)) >>> 0;
}
console.log(reverseBitsSimple(5)); // Same as reverseBits
console.log(swapAdjacentBits(0b10110100)); // 0b01101000
console.log(swapNibbles(0x12345678).toString(16)); // 0x21436587
console.log(reverseBytes(0x12345678).toString(16)); // 0x78563412
Note: Use
>>> (unsigned right shift) instead of >> when working with bit reversal to avoid sign extension issues with negative numbers. The mask 0xAAAAAAAA = all odd bits, 0x55555555 = all even bits.
Summary: Bit Manipulation Pattern
- Bitmasking: Use integers as sets - iterate 2n subsets with
for (mask=0; mask<(1<<n); mask++) - Subset Generation: Powers of 2 are single bits; iterate submasks with
s=(s-1)&mask - Counting Bits: Brian Kernighan's
n&(n-1)removes rightmost bit - O(k) for k set bits - XOR Properties:
a^a=0,a^0=a- perfect for finding unique elements in duplicates - Bit Tricks:
n<<k= multiply by 2k,n>>k= divide by 2k,n&1= check odd/even - Hamming Distance: Count bits in
x^y- for arrays, count per bit position - Power of 2: Check with
n>0 && (n&(n-1))===0- exactly one bit set - Gray Code:
binary^(binary>>1)- adjacent codes differ by 1 bit - Gosper's Hack: Generate next k-combination efficiently - maintains bit count
- Reverse Bits: Swap progressively smaller chunks - 16-bit, 8-bit, 4-bit, 2-bit, 1-bit
- Key Insight: Bits can represent sets, states, and choices - enables compact DP and combinatorial algorithms