Bit Manipulation in Data Structures

Fundamentals of Binary Representation

Computers represent all data — integers, floats, characters, even images — as sequences of bits (0 and 1). Understanding how numbers are stored in binary is the foundation of bit manipulation.

Decimal to Binary Conversion

To convert decimal to binary, repeatedly divide by 2 and collect remainders:

13 ÷ 2 = 6 remainder 1
 6 ÷ 2 = 3 remainder 0
 3 ÷ 2 = 1 remainder 1
 1 ÷ 2 = 0 remainder 1

Read remainders bottom-up: 13 = 1101 in binary

Integer Bit Layout (32-bit signed)

In a standard 32-bit signed integer using Two's Complement representation:

• Bit 31 (leftmost): Sign bit — 0 = positive, 1 = negative
• Bits 0-30: Store the magnitude

Decimal 13  →  Binary: 00000000 00000000 00000000 00001101
Decimal -1  →  Binary: 11111111 11111111 11111111 11111111
Decimal -13 →  Binary: 11111111 11111111 11111111 11110011

Two's Complement of a number: flip all bits, then add 1. This ensures -13 + 13 = 0 in binary arithmetic.

Core Bitwise Operators

Code Examples:

JavaScript:

javascript
const a = 5;   // 0101
const b = 3;   // 0011

console.log(a & b);   // 1  → 0001
console.log(a | b);   // 7  → 0111
console.log(a ^ b);   // 6  → 0110
console.log(~a);      // -6 (Two's Complement: flip all bits of 5)
console.log(a << 1);  // 10 → 1010 (×2)
console.log(a >> 1);  // 2  → 0010 (÷2)

Python:

python
a, b = 5, 3
print(a & b)    # 1
print(a | b)    # 7
print(a ^ b)    # 6
print(~a)       # -6
print(a << 1)   # 10
print(a >> 1)   # 2

Essential Bit Tricks

These are the building blocks for most bit manipulation interview problems:

1. Check if a Number is Even or Odd

javascript
function isEven(n) {
    return (n & 1) === 0;   // Last bit 0 = even, 1 = odd
}
console.log(isEven(4));  // true
console.log(isEven(7));  // false

Why it works: Even numbers in binary always end in 0. n & 1 extracts just the last bit.

2. Check if a Number is a Power of Two

javascript
function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}
// Powers of 2: 1(001), 2(010), 4(100), 8(1000)
// n & (n-1) clears the lowest set bit
// If n is a power of 2, it has exactly ONE set bit
// Clearing that bit gives 0
console.log(isPowerOfTwo(16)); // true  (10000 & 01111 = 0)
console.log(isPowerOfTwo(12)); // false (01100 & 01011 = 01000 ≠ 0)

3. Get the i-th Bit (0-indexed from right)

javascript
function getBit(n, i) {
    return (n >> i) & 1;
}
// For n=13 (1101):
// getBit(13, 0) = 1  (rightmost bit)
// getBit(13, 2) = 1  (third bit from right)
// getBit(13, 1) = 0  (second bit from right)

4. Set the i-th Bit (force it to 1)

javascript
function setBit(n, i) {
    return n | (1 << i);
}
// setBit(9, 1): 1001 | 0010 = 1011 = 11

5. Clear the i-th Bit (force it to 0)

javascript
function clearBit(n, i) {
    return n & ~(1 << i);
}
// clearBit(15, 1): 1111 & ~(0010) = 1111 & 1101 = 1101 = 13

6. Toggle the i-th Bit (flip 0→1 or 1→0)

javascript
function toggleBit(n, i) {
    return n ^ (1 << i);
}
// toggleBit(10, 1): 1010 ^ 0010 = 1000 = 8
// toggleBit(8, 1):  1000 ^ 0010 = 1010 = 10

7. Count Set Bits (Brian Kernighan's Algorithm)

javascript
function countSetBits(n) {
    let count = 0;
    while (n > 0) {
        n = n & (n - 1);   // Clear the lowest set bit
        count++;
    }
    return count;
}
// countSetBits(13) → 13=1101 has 3 set bits → returns 3

Why it works: n & (n-1) always clears the rightmost 1 bit. The loop runs exactly as many times as there are set bits.

8. Find the Lowest Set Bit

javascript
function lowestSetBit(n) {
    return n & (-n);
}
// For n = 12 (1100): -12 in two's complement = 0100
// 1100 & 0100 = 0100 = 4 (the lowest set bit)

XOR Properties — The Magic Trick

XOR has unique mathematical properties that make it extremely powerful:

Application: Find the Single Non-Duplicate Number

Given an array where every element appears twice except one, find that one:

javascript
function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;   // XOR all numbers together
    }
    return result;
}

// Example: [4, 1, 2, 1, 2]
// 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4
console.log(singleNumber([4, 1, 2, 1, 2]));  // Output: 4
console.log(singleNumber([2, 2, 1]));          // Output: 1

Why it works: Pairs cancel out (X ^ X = 0), and the single number XORed with 0 is itself (X ^ 0 = X).

Application: Swap Two Numbers Without a Temp Variable

javascript
function swapWithXOR(a, b) {
    a = a ^ b;    // a now holds info about both
    b = a ^ b;    // b = (a^b)^b = a
    a = a ^ b;    // a = (a^b)^a = b
    return [a, b];
}
console.log(swapWithXOR(5, 3));  // [3, 5]

Bitmask Applications

Representing Subsets as Bitmasks

A bitmask is an integer where each bit represents whether an element is "included" in a subset. For a set of N elements, each possible subset maps to a unique integer from 0 to 2^N - 1.

javascript
// For set [A, B, C]:
// 000 = {} (empty)
// 001 = {A}
// 010 = {B}
// 011 = {A, B}
// 100 = {C}
// 101 = {A, C}
// 110 = {B, C}
// 111 = {A, B, C}

function generateAllSubsets(arr) {
    const n = arr.length;
    const subsets = [];

    for (let mask = 0; mask < (1 << n); mask++) {  // 0 to 2^n - 1
        const subset = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {    // Check if i-th bit is set
                subset.push(arr[i]);
            }
        }
        subsets.push(subset);
    }

    return subsets;
}

console.log(generateAllSubsets(['A', 'B', 'C']));
// [[], ['A'], ['B'], ['A','B'], ['C'], ['A','C'], ['B','C'], ['A','B','C']]

Bitmask Dynamic Programming (Bitmask DP)

Bitmask DP tracks sets of visited states using an integer bitmask. It's used to solve NP-hard problems over small inputs (N ≤ 20).

Travelling Salesman Problem (TSP) with Bitmask DP

Find the minimum cost tour visiting all N cities exactly once and returning to the start:

javascript
function tsp(dist) {
    const n = dist.length;
    const FULL = (1 << n) - 1;    // All cities visited bitmask
    const dp = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));

    dp[1][0] = 0;    // Start at city 0, only city 0 visited

    for (let mask = 1; mask <= FULL; mask++) {
        for (let u = 0; u < n; u++) {
            if (dp[mask][u] === Infinity) continue;
            if (!(mask & (1 << u))) continue;   // u must be in mask

            for (let v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;  // v already visited

                const newMask = mask | (1 << v);
                dp[newMask][v] = Math.min(
                    dp[newMask][v],
                    dp[mask][u] + dist[u][v]
                );
            }
        }
    }

    // Return to city 0 from each possible last city
    let minCost = Infinity;
    for (let u = 1; u < n; u++) {
        minCost = Math.min(minCost, dp[FULL][u] + dist[u][0]);
    }

    return minCost;
}

Time Complexity: $O(2^N \times N^2)$, Space: $O(2^N \times N)$ — feasible for N ≤ 20.

Advantages and Disadvantages

Complexity Reference

Real World Usages

• Unix File Permissions: chmod 755 represents rwxr-xr-x — each permission is a bit: read(4), write(2), execute(1). 7 = 4+2+1 = 111.
• Compression & Encryption: Huffman coding builds variable-length bit sequences; AES and DES cryptographic algorithms operate entirely on bitwise XOR, AND, shifts.
• Network Routing & Subnet Masks: An IP subnet mask like 255.255.255.0 is a 32-bit bitmask. ANDing an IP address with the mask extracts the network prefix.
• Game Development (Flags): Bitflags pack multiple game entity states (isVisible, isActive, hasGravity, isDead) into a single integer, enabling fast state testing.
• Graphics & Rendering: Alpha blending and color component extraction use bitwise operations on pixel values (RGBA packed in 32 bits).
• Hash Tables: Many hash functions use XOR mixing to combine hash values for better distribution.

Common Interview Patterns

1. Single Number: Find the element that appears once while others appear twice — XOR all elements.
2. Hamming Weight / Number of 1 Bits: Count set bits using Brian Kernighan or built-ins.
3. Power of Two Check: n > 0 && (n & n-1) == 0.
4. Reverse Bits: Reverse the 32-bit binary representation of an integer.
5. Missing Number in Range [0, N]: XOR all indices with all array values.
6. Counting Bits: For every number from 0 to N, count the number of 1s (use DP: dp[i] = dp[i >> 1] + (i & 1)).
7. Bitmask Subset Enumeration: Iterate over all subsets of a bitmask using for (let sub = mask; sub > 0; sub = (sub-1) & mask).

Frequently Asked Questions

Q: Why does ~5 = -6 in JavaScript/Java/C++?
A: ~ flips all bits. 5 in 32-bit binary is 00000000 00000000 00000000 00000101. Flipping gives 11111111 11111111 11111111 11111010. In Two's Complement representation, this is -6. In general, ~n = -(n+1) for any integer n.

Q: What is the difference between >> and >>> in JavaScript?
A: >> is a signed right shift — it preserves the sign bit (fills with the MSB). >>> is an unsigned right shift — it always fills with 0, treating the number as unsigned. Use >>> 0 to convert a negative number to its unsigned 32-bit equivalent.

Q: Why is n & (n-1) special?
A: n & (n-1) always clears the lowest set bit of n. This is because n-1 flips all the bits from the lowest set bit rightward. Applications: (1) check if n is a power of 2, (2) Brian Kernighan's algorithm to count set bits, (3) find the largest power of 2 dividing n.

Q: What is bitmask DP and when should I use it?
A: Bitmask DP uses an integer to represent a set of visited elements, where the i-th bit being set means element i is in the set. It's used when: (1) N is small (≤ 20), (2) the problem requires tracking subsets or combinations of elements. Classic problems: Travelling Salesman, Set Cover, Assignment Problem.

Q: How do I iterate over all non-empty subsets of a bitmask?
A: Use this classic trick:

javascript
for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // `sub` is a valid subset of `mask`
}

This visits all $2^k$ subsets of a mask with $k$ set bits, in decreasing order.