Bit Manipulation Problem Types

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

function traditionalSwap(a: number, b: number): [number, number] {
    // Before: a = originalA, b = originalB
    
    const temp = a;  // Step 1: Save 'a' in temporary storage
                     // State: temp = originalA, a = originalA, b = originalB
    
    a = b;           // Step 2: Overwrite 'a' with 'b'
                     // State: temp = originalA, a = originalB, b = originalB
    
    b = temp;        // Step 3: Assign saved value to 'b'
                     // State: temp = originalA, a = originalB, b = originalA
    
    // After: a = originalB, b = originalA (swapped!)
    return [a, b];
}
 
// Example execution trace:
console.log(traditionalSwap(42, 17));
// Output: [17, 42]

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

// Let's verify each property with concrete examples
const a = 42;  // Binary: 00101010
const b = 17;  // Binary: 00010001
 
// Property 1: Self-Inverse
console.log("a ⊕ a =", a ^ a);  // Output: 0
// 00101010 ⊕ 00101010 = 00000000
 
// Property 2: Identity with Zero
console.log("a ⊕ 0 =", a ^ 0);  // Output: 42
// 00101010 ⊕ 00000000 = 00101010
 
// Property 3: Commutativity
console.log("a ⊕ b =", a ^ b);  // Output: 59
console.log("b ⊕ a =", b ^ a);  // Output: 59
// Both are 00111011
 
// Property 4: Associativity
const c = 99;  // Binary: 01100011
console.log("(a ⊕ b) ⊕ c =", (a ^ b) ^ c);  // Output: 88
console.log("a ⊕ (b ⊕ c) =", a ^ (b ^ c));  // Output: 88
 
// Property 5: Invertibility
const combined = a ^ b;  // 59
console.log("combined ⊕ b =", combined ^ b);  // Output: 42 (recovers a!)
console.log("combined ⊕ a =", combined ^ a);  // Output: 17 (recovers b!)

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

function xorSwap(a: number, b: number): [number, number] {
    // Initial state: a = A, b = B (using capitals for original values)
    
    a = a ^ b;  // Step 1: a now holds A ⊕ B
                // State: a = A⊕B, b = B
    
    b = b ^ a;  // Step 2: b = B ⊕ (A⊕B) = A
                // State: a = A⊕B, b = A
    
    a = a ^ b;  // Step 3: a = (A⊕B) ⊕ A = B
                // State: a = B, b = A
    
    // After: a = B, b = A (swapped!)
    return [a, b];
}
 
// Example execution:
console.log(xorSwap(42, 17));  // Output: [17, 42]

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

function xorSwapInPlace(arr: number[], i: number, j: number): void {
    // Dangerous! What if i === j?
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}
 
// Normal case: works correctly
const arr1 = [10, 20, 30, 40, 50];
console.log("Before:", arr1);  // [10, 20, 30, 40, 50]
xorSwapInPlace(arr1, 1, 3);
console.log("After:", arr1);   // [10, 40, 30, 20, 50] ✓
 
// Bug case: self-swap destroys data!
const arr2 = [10, 20, 30, 40, 50];
console.log("Before:", arr2);  // [10, 20, 30, 40, 50]
xorSwapInPlace(arr2, 2, 2);    // Swapping index 2 with itself
console.log("After:", arr2);   // [10, 20, 0, 40, 50] ✗ Data lost!

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

function safeXorSwapInPlace(arr: number[], i: number, j: number): void {
    // Guard clause prevents the self-swap bug
    if (i === j) {
        return;  // Nothing to swap; early exit preserves value
    }
    
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}
 
// Now both cases work correctly
const arr = [10, 20, 30, 40, 50];
safeXorSwapInPlace(arr, 1, 3);
console.log(arr);  // [10, 40, 30, 20, 50] ✓
 
safeXorSwapInPlace(arr, 2, 2);
console.log(arr);  // [10, 40, 30, 20, 50] ✓ (unchanged, as expected)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function arithmeticSwap(a: number, b: number): [number, number] {
    // Using addition and subtraction
    a = a + b;  // a now holds sum
    b = a - b;  // b = sum - oldB = oldA
    a = a - b;  // a = sum - newB = sum - oldA = oldB
    
    return [a, b];
}
 
console.log(arithmeticSwap(42, 17));  // [17, 42]
 
// Warning: This has overflow issues for large numbers!
// For 32-bit signed integers:
// MAX_INT = 2,147,483,647
// If a = 2,000,000,000 and b = 1,000,000,000
// a + b = 3,000,000,000 > MAX_INT → overflow!

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

function multiplicativeSwap(a: number, b: number): [number, number] {
    // Only works when b !== 0!
    if (b === 0 && a !== 0) {
        throw new Error("Cannot swap when b=0 and a≠0 using multiplication");
    }
    
    if (a === 0 || b === 0) {
        // Special case: one is zero
        return [b, a];  // Just return swapped values
    }
    
    a = a * b;  // a now holds product
    b = a / b;  // b = product / oldB = oldA
    a = a / b;  // a = product / newB = product / oldA = oldB
    
    return [a, b];
}
 
// Works for non-zero values
console.log(multiplicativeSwap(42, 17));  // [17, 42]
 
// But has division issues:
// - Division by zero if b = 0
// - Floating point precision loss for non-integer results
// - Overflow for large numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// On modern out-of-order CPUs:
 
// Traditional swap (can be parallelized by CPU):
// These are independent operations that can use rename registers
temp = a;  // Can execute in parallel with next line
a = b;     // Can execute in parallel with previous line
b = temp;  // Depends only on temp, not on the new 'a'
 
// XOR swap (serialized due to dependencies):
a = a ^ b;  // Must complete first
b = b ^ a;  // Must wait for new 'a' — data dependency
a = a ^ b;  // Must wait for new 'b' — data dependency
 
// The XOR swap creates a chain of dependencies that prevents
// instruction-level parallelism that modern CPUs rely on for speed.

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

function xorCipher(data: number[], key: number): number[] {
    // XOR encryption: same operation encrypts and decrypts!
    // This is the basis of one-time pad encryption
    return data.map(byte => byte ^ key);
}
 
const original = [72, 101, 108, 108, 111];  // "Hello" as ASCII
const key = 42;
 
const encrypted = xorCipher(original, key);
console.log("Encrypted:", encrypted);  // [114, 79, 70, 70, 69]
 
const decrypted = xorCipher(encrypted, key);  // Same operation!
console.log("Decrypted:", decrypted);  // [72, 101, 108, 108, 111]
console.log("As string:", String.fromCharCode(...decrypted));  // "Hello"
 
// This works because: (data ⊕ key) ⊕ key = data
// The self-inverse property makes XOR ideal for symmetric operations

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

// A memory-efficient doubly-linked list using XOR!
// Each node stores: npx = prev_address ⊕ next_address
// This halves the pointer storage compared to standard doubly-linked lists
 
interface XorNode {
    data: number;
    npx: number;  // XOR of next and previous node addresses
}
 
// Conceptual traversal (in a language with raw pointers):
// 
// To go forward from node A to node B:
//   next_addr = prev_addr ^ current.npx
//
// To go backward from node B to node A:  
//   prev_addr = next_addr ^ current.npx
//
// Example:
// Nodes at addresses: [100] <-> [200] <-> [300]
//
// Node at 100: npx = 0 ^ 200 = 200 (prev is NULL/0)
// Node at 200: npx = 100 ^ 300 = 400
// Node at 300: npx = 200 ^ 0 = 200 (next is NULL/0)
//
// Traversing forward from 100 to 200:
//   prev = 0 (start), current = 100
//   next = prev ^ current.npx = 0 ^ 200 = 200 ✓
//
// Traversing forward from 200 to 300:
//   prev = 100, current = 200
//   next = prev ^ current.npx = 100 ^ 400 = 300 ✓
 
console.log("XOR Linked List reduces memory by eliminating one pointer per node");