When to Use Bit Manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/**
 * Demonstrating the performance difference between
 * manual bit counting vs. built-in operations.
 * 
 * Note: JavaScript doesn't expose POPCNT directly,
 * but TypedArrays allow efficient operations.
 * For real performance, use WebAssembly or native code.
 */
 
// Manual bit counting - O(number of bits)
function popcountManual(n: number): number {
    let count = 0;
    while (n) {
        count++;
        n &= (n - 1); // Clear lowest set bit
    }
    return count;
}
 
// Brian Kernighan's algorithm - O(number of set bits)
function popcountKernighan(n: number): number {
    let count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}
 
// Parallel bit counting - constant time O(1)
// Uses SWAR (SIMD Within A Register) technique
function popcountParallel(n: number): number {
    // Handle only 32 bits (JavaScript limitation)
    n = n >>> 0; // Convert to unsigned 32-bit
    
    // Step 1: Count bits in pairs
    n = n - ((n >>> 1) & 0x55555555);
    
    // Step 2: Count bits in nibbles  
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
    
    // Step 3: Count bits in bytes
    n = (n + (n >>> 4)) & 0x0F0F0F0F;
    
    // Step 4: Sum all bytes using multiply
    n = (n * 0x01010101) >>> 24;
    
    return n;
}
 
// In production JavaScript, Math.clz32 provides leading zeros
function leadingZeros(n: number): number {
    return Math.clz32(n); // Hardware-accelerated on V8
}
 
// Trailing zeros via leading zeros and popcount
function trailingZeros(n: number): number {
    if (n === 0) return 32;
    // n & -n isolates lowest set bit
    // clz32 of that gives 31 - position of that bit
    return 31 - Math.clz32(n & -n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// Example: Next power of 2
// Clear code - compiler may not optimize fully
function nextPowerOf2_clear(n: number): number {
    if (n <= 0) return 1;
    if ((n & (n - 1)) === 0) return n; // Already power of 2
    
    let power = 1;
    while (power < n) {
        power *= 2;
    }
    return power;
}
 
// Bit manipulation - definitely O(log(bits)) operations
function nextPowerOf2_bits(n: number): number {
    if (n <= 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}
 
// Using built-in (preferred when available)
function nextPowerOf2_builtin(n: number): number {
    if (n <= 0) return 1;
    if ((n & (n - 1)) === 0) return n;
    
    // 2^(32 - clz32(n - 1))
    return 1 << (32 - Math.clz32(n - 1));
}
 
// All three produce the same result, but performance varies
// The built-in version is typically fastest and clearest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Branching version - bad if condition is unpredictable
function maxBranching(a: number, b: number): number {
    return a > b ? a : b;
}
 
// Branchless version using bit manipulation
function maxBranchless(a: number, b: number): number {
    // Works for signed 32-bit integers
    const diff = a - b;
    const mask = diff >> 31; // All 0s if a >= b, all 1s if a < b
    return a - (diff & mask);
}
 
// Modern alternative: Math.max is often optimized by engine
function maxBuiltin(a: number, b: number): number {
    return Math.max(a, b);
}
 
// When to use branchless:
// - Processing large arrays with random comparison outcomes
// - Inner loops where branch prediction fails
// - When profiling shows branch misprediction bottleneck
 
// When branching is fine:
// - Predictable patterns (sorted data, mostly equal values)
// - Compiler already generates branchless code (check assembly)
// - Clarity matters more than microseconds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/**
 * Demonstration of cache effects on bit manipulation performance.
 * 
 * This example counts set bits across large arrays.
 * The bit-packed version is faster primarily due to cache effects.
 */
 
function countTrueBooleans(arr: boolean[]): number {
    let count = 0;
    for (const val of arr) {
        if (val) count++;
    }
    return count;
}
 
function countSetBits(bits: Uint32Array, totalBits: number): number {
    let count = 0;
    const fullWords = Math.floor(totalBits / 32);
    
    for (let i = 0; i < fullWords; i++) {
        // Parallel bit count - processes 32 bits per loop iteration
        let n = bits[i];
        n = n - ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n + (n >>> 4)) & 0x0F0F0F0F;
        count += (n * 0x01010101) >>> 24;
    }
    
    // Handle remaining bits in last partial word
    const remaining = totalBits % 32;
    if (remaining > 0) {
        const mask = (1 << remaining) - 1;
        let n = bits[fullWords] & mask;
        n = n - ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n + (n >>> 4)) & 0x0F0F0F0F;
        count += (n * 0x01010101) >>> 24;
    }
    
    return count;
}
 
// For truly optimal performance:
// 1. Process data in cache-line-sized chunks (64 bytes)
// 2. Prefetch future data while processing current data
// 3. Use SIMD instructions when available (WebAssembly SIMD)
 
/**
 * Cache-oblivious algorithm pattern:
 * Process data in chunks that will fit in cache,
 * without needing to know the exact cache size.
 */
function processInChunks<T>(
    data: T[],
    chunkSize: number,
    processor: (chunk: T[]) => void
): void {
    for (let i = 0; i < data.length; i += chunkSize) {
        const chunk = data.slice(i, i + chunkSize);
        processor(chunk);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// BAD: Result is never used - may be optimized away
function badBenchmark(): void {
    const start = performance.now();
    
    for (let i = 0; i < 1000000; i++) {
        const result = someOperation(i); // Result unused!
    }
    
    console.log(`Time: ${performance.now() - start}ms`);
}
 
// GOOD: Accumulate results to prevent dead code elimination
function goodBenchmark(): number {
    const start = performance.now();
    let accumulator = 0;
    
    for (let i = 0; i < 1000000; i++) {
        accumulator += someOperation(i);
    }
    
    const elapsed = performance.now() - start;
    console.log(`Time: ${elapsed}ms`);
    
    return accumulator; // Return to ensure computation happens
}
 
// For V8/JavaScript: Use blackhole pattern
const blackhole = {
    value: 0,
    consume(x: number): void {
        this.value += x;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

interface BenchmarkResult {
    coldTime: number;
    warmTime: number;
    warmIterations: number;
}
 
function benchmarkWithCacheInfo(
    data: Uint32Array,
    operation: (data: Uint32Array) => number,
    warmupRuns: number = 5,
    measuredRuns: number = 100
): BenchmarkResult {
    // Cold run (data not in cache)
    // Force data out of cache first (not always possible in JS)
    const coldStart = performance.now();
    const coldResult = operation(data);
    const coldTime = performance.now() - coldStart;
    
    // Warmup runs to stabilize JIT and populate caches
    for (let i = 0; i < warmupRuns; i++) {
        operation(data);
    }
    
    // Measured warm runs
    const warmStart = performance.now();
    for (let i = 0; i < measuredRuns; i++) {
        operation(data);
    }
    const warmTime = (performance.now() - warmStart) / measuredRuns;
    
    return {
        coldTime,
        warmTime,
        warmIterations: measuredRuns
    };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

interface StatisticalResult {
    median: number;
    mean: number;
    stdDev: number;
    min: number;
    max: number;
    p95: number;
}
 
function statisticalBenchmark(
    operation: () => void,
    iterations: number = 1000
): StatisticalResult {
    const times: number[] = [];
    
    // Warmup
    for (let i = 0; i < 100; i++) {
        operation();
    }
    
    // Measured runs
    for (let i = 0; i < iterations; i++) {
        const start = performance.now();
        operation();
        times.push(performance.now() - start);
    }
    
    // Sort for percentile calculations
    times.sort((a, b) => a - b);
    
    // Statistical calculations
    const sum = times.reduce((a, b) => a + b, 0);
    const mean = sum / times.length;
    
    const squaredDiffs = times.map(t => (t - mean) ** 2);
    const variance = squaredDiffs.reduce((a, b) => a + b, 0) / times.length;
    const stdDev = Math.sqrt(variance);
    
    return {
        median: times[Math.floor(times.length / 2)],
        mean,
        stdDev,
        min: times[0],
        max: times[times.length - 1],
        p95: times[Math.floor(times.length * 0.95)]
    };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Set intersection: typical array approach
function intersectArrays(a: boolean[], b: boolean[]): boolean[] {
    const result: boolean[] = [];
    for (let i = 0; i < a.length; i++) {
        result.push(a[i] && b[i]);
    }
    return result; // O(n) iterations, n boolean ops
}
 
// Set intersection: bit array approach
function intersectBitArrays(a: Uint32Array, b: Uint32Array): Uint32Array {
    const result = new Uint32Array(a.length);
    for (let i = 0; i < a.length; i++) {
        result[i] = a[i] & b[i];
    }
    return result; // O(n/32) iterations, n/32 AND ops
}
 
// For 1 million elements:
// Array: 1 million loop iterations, 1 million boolean ANDs
// BitArray: ~31,250 loop iterations, ~31,250 32-bit ANDs
// Speedup: ~32× fewer operations + better cache behavior

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Recursive subset generation
function* recursiveSubsets<T>(arr: T[], index = 0, current: T[] = []): Generator<T[]> {
    if (index === arr.length) {
        yield [...current];
        return;
    }
    
    // Exclude current element
    yield* recursiveSubsets(arr, index + 1, current);
    
    // Include current element
    current.push(arr[index]);
    yield* recursiveSubsets(arr, index + 1, current);
    current.pop();
}
 
// Bitmask iteration
function* bitmaskSubsets(n: number): Generator<number> {
    for (let mask = 0; mask < (1 << n); mask++) {
        yield mask;
    }
}
 
// Converting mask to array subset
function maskToSubset<T>(arr: T[], mask: number): T[] {
    const result: T[] = [];
    for (let i = 0; mask; i++, mask >>>= 1) {
        if (mask & 1) {
            result.push(arr[i]);
        }
    }
    return result;
}
 
// Bitmask is faster because:
// 1. No function call overhead per subset
// 2. No array allocation/deallocation per recursive call
// 3. Cache-friendly sequential integer iteration
// 4. Modern CPUs optimize tight counting loops extremely well

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Ring buffer index calculation - common pattern
class RingBuffer<T> {
    private data: T[];
    private head = 0;
    private tail = 0;
    private mask: number; // For bitwise modulo
    
    // IMPORTANT: size must be power of 2
    constructor(size: number) {
        if ((size & (size - 1)) !== 0) {
            throw new Error("Size must be power of 2");
        }
        this.data = new Array(size);
        this.mask = size - 1;
    }
    
    // Slower: using modulo
    private wrapIndexSlow(index: number): number {
        return index % this.data.length;
    }
    
    // Faster: using bitwise AND
    private wrapIndexFast(index: number): number {
        return index & this.mask;
    }
    
    push(item: T): void {
        this.data[this.tail] = item;
        this.tail = (this.tail + 1) & this.mask;
    }
    
    pop(): T | undefined {
        if (this.head === this.tail) return undefined;
        const item = this.data[this.head];
        this.head = (this.head + 1) & this.mask;
        return item;
    }
}
 
// In tight loops (hash table probing, audio buffers, network packets),
// this difference is measurable: modulo takes 10-90 cycles,
// bitwise AND takes 1 cycle.