Bit Manipulation

Bitwise operators work on individual bits of integers:

// AND (&) — both bits must be 1
5 & 3   // 101 & 011 = 001 = 1

// OR (|) — at least one bit must be 1
5 | 3   // 101 | 011 = 111 = 7

// XOR (^) — bits must differ
5 ^ 3   // 101 ^ 011 = 110 = 6

// Key XOR properties:
// a ^ a = 0, a ^ 0 = a, a ^ b ^ a = b

AND masks bits, OR sets bits, XOR toggles bits and detects differences.

Left shift (<<) multiplies by 2n. Right shift (>>) divides by 2n (integer division).

// Left shift: a << n = a * 2^n
5 << 1   // 101 -> 1010 = 10
5 << 2   // 101 -> 10100 = 20

// Right shift: a >> n = Math.floor(a / 2^n)
20 >> 1  // 10100 -> 1010 = 10
20 >> 2  // 10100 -> 101 = 5

// Common use: mid = (lo + hi) >> 1  (same as Math.floor((lo+hi)/2))

Shifts are faster than multiplication/division and commonly used in low-level optimization.

A power of 2 has exactly one bit set. The trick: n & (n - 1) clears the lowest set bit. If the result is 0, it was a power of 2.

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}
// 8  = 1000, 7  = 0111 => 1000 & 0111 = 0 ✓
// 6  = 0110, 5  = 0101 => 0110 & 0101 = 4 ✗

isPowerOfTwo(16) // true  (10000)
isPowerOfTwo(18) // false (10010)

Time: O(1) | Space: O(1)

Count how many bits are 1 in a number. Use n & (n - 1) to clear the lowest set bit each iteration.

function countSetBits(n) {
    let count = 0;
    while (n) {
        n &= (n - 1); // clear lowest set bit
        count++;
    }
    return count;
}
// 13 = 1101 => 3 set bits
// 7  = 0111 => 3 set bits
// 16 = 10000 => 1 set bit
countSetBits(13) // 3

Time: O(number of set bits) | Space: O(1)

In an array where every element appears twice except one, XOR all elements. Pairs cancel out (a ^ a = 0), leaving the single number.

function singleNumber(nums) {
    let result = 0;
    for (const n of nums) {
        result ^= n;
    }
    return result;
}
// singleNumber([4, 1, 2, 1, 2]) => 4
// 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4

Time: O(n) | Space: O(1) — no extra data structure needed.

Use XOR to swap: a ^= b; b ^= a; a ^= b;. This works because XOR is its own inverse.

function swap(a, b) {
    a = a ^ b;  // a now holds a^b
    b = a ^ b;  // b = (a^b)^b = a
    a = a ^ b;  // a = (a^b)^a = b
    return [a, b];
}
// swap(5, 3) => [3, 5]
// Step by step: a=5(101), b=3(011)
// a = 101^011 = 110 (6)
// b = 110^011 = 101 (5) = original a
// a = 110^101 = 011 (3) = original b

Note: In practice, a temporary variable is simpler and preferred. XOR swap fails if a and b are the same reference.

Use XOR with a mask that has only the nth bit set: n ^ (1 << pos).

// Toggle bit at position pos
function toggleBit(n, pos) {
    return n ^ (1 << pos);
}

// Set bit:   n | (1 << pos)
// Clear bit: n & ~(1 << pos)
// Check bit: (n >> pos) & 1

toggleBit(10, 0)  // 1010 ^ 0001 = 1011 (11)
toggleBit(11, 0)  // 1011 ^ 0001 = 1010 (10)
toggleBit(10, 2)  // 1010 ^ 0100 = 1110 (14)

XOR flips the targeted bit: 0 becomes 1 and 1 becomes 0.

XOR all elements to get xor = a ^ b. Find a set bit (the two differ here). Partition elements by that bit to separate a and b.

function findTwoNonRepeating(nums) {
    let xor = 0;
    for (const n of nums) xor ^= n;
    const setBit = xor & (-xor); // lowest set bit
    let a = 0, b = 0;
    for (const n of nums) {
        if (n & setBit) a ^= n;
        else b ^= n;
    }
    return [a, b];
}
// findTwoNonRepeating([1, 2, 3, 1, 2, 5])
// => [3, 5]

Time: O(n) | Space: O(1)

Process each bit from right to left, building the reversed number by shifting and adding bits.

function reverseBits(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result >>> 0; // unsigned
}
// reverseBits(0b00000000000000000000000000001011)
// => 0b11010000000000000000000000000000
// = 3489660928

Time: O(32) = O(1) | Space: O(1)

For n elements, iterate from 0 to 2n-1. Each number represents a subset: bit j set means include element j.

function subsets(arr) {
    const n = arr.length;
    const result = [];
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            if (mask & (1 << j)) subset.push(arr[j]);
        }
        result.push(subset);
    }
    return result;
}
// subsets([1, 2, 3])
// => [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Total subsets: 2n | Time: O(n × 2n)

Use n & (n-1) to clear the lowest set bit repeatedly and count iterations. Alternative: use Brian Kernighan's algorithm.

function hammingWeight(n) {
    let count = 0;
    while (n) {
        n &= (n - 1); // clears the lowest set bit
        count++;
    }
    return count;
}
// Input: n=11 (1011 in binary)  => Output: 3  (three 1-bits)
// Input: n=128 (10000000)        => Output: 1
// Input: n=4294967293 (0b11111111111111111111111111111101) => Output: 31

// Using bit shift:
function countBits(n) {
    let count = 0;
    while (n) { count += n & 1; n >>>= 1; }
    return count;
}

Time: O(k) where k is the number of set bits (= O(log n) worst case) | Space: O(1)

XOR all numbers 0..n AND all array elements. Paired numbers cancel out; the unpaired one is the missing number.

function missingNumber(nums) {
    let xor = nums.length; // start with n
    for (let i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}
// Input: [3,0,1]    => Output: 2
// Input: [0,1]      => Output: 2
// Input: [9,6,4,2,3,5,7,0,1] => Output: 8

Time: O(n) | Space: O(1)

Alternative: sum formula: n*(n+1)/2 - sum(nums). XOR avoids potential overflow.

XOR all elements to get x = a^b. Find any set bit in x (a and b differ there). Split array into two groups by that bit; XOR each group to isolate a and b.

function twoSingleNumbers(nums) {
    let xor = 0;
    for (const n of nums) xor ^= n; // xor = a ^ b
    // Find rightmost set bit (where a and b differ)
    const setBit = xor & (-xor); // isolates lowest set bit
    let a = 0, b = 0;
    for (const n of nums) {
        if (n & setBit) a ^= n; // group with this bit set
        else b ^= n;            // group without this bit
    }
    return [a, b];
}
// Input: [1,2,3,4,1,2]   => Output: [3,4]
// Input: [2,3,7,9,11,2,3,11] => Output: [7,9]

Time: O(n) | Space: O(1)

Use a mask. Shift left into result's MSB while shifting right through input's bits. Process all 32 bit positions.

function reverseBits(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1); // add LSB of n to MSB of result
        n >>>= 1; // unsigned right shift
    }
    return result >>> 0; // ensure unsigned 32-bit
}
// Input: 43261596          (binary: 00000010100101000001111010011100)
// Output: 964176192        (binary: 00111001011110000010100101000000)
// Input: 4294967293        (binary: 11111111111111111111111111111101)
// Output: 3221225471       (binary: 10111111111111111111111111111111)

Time: O(32) = O(1) | Space: O(1)

For an array of n elements, there are 2ⁿ subsets. Use a bitmask from 0 to 2ⁿ-1; each bit represents whether to include the corresponding element.

function subsets(nums) {
    const n = nums.length;
    const result = [];
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push(nums[i]);
        }
        result.push(subset);
    }
    return result;
}
// Input: [1,2,3]  => Output: 8 subsets (2^3)
// mask=0 (000) => [], mask=1 (001) => [1], mask=7 (111) => [1,2,3]
// Input: [1,2]   => Output: [[],[1],[2],[1,2]]

Time: O(2ⁿ × n) | Space: O(n) per subset

XOR all elements — duplicates cancel out, leaving the single element. For a sorted array, you can also use binary search: at the single element's position, the pair ordering breaks.

// XOR approach (O(n)):
function singleNonDuplicate(nums) {
    return nums.reduce((xor, n) => xor ^ n, 0);
}
// Binary search on sorted array (O(log n)):
function singleNonDuplicateBSearch(nums) {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        let mid = Math.floor((lo + hi) / 2);
        if (mid % 2 === 1) mid--; // ensure mid is even
        if (nums[mid] === nums[mid + 1]) lo = mid + 2; // single is on right
        else hi = mid;                                 // single is here or left
    }
    return nums[lo];
}
// Input: [1,1,2,3,3,4,4,8,8]  => Output: 2
// Input: [3,3,7,7,10,11,11]   => Output: 10

Time: O(log n) binary search | Space: O(1)

Use the XOR swap trick: a = a^b, b = a^b, a = a^b. Works because XOR is its own inverse. Note: fails if a and b are the same variable/reference.

function xorSwap(a, b) {
    a = a ^ b;
    b = a ^ b; // b = (a^b)^b = a
    a = a ^ b; // a = (a^b)^a = b
    return [a, b];
}
// Input: a=5, b=3   => Output: a=3, b=5
// Trace: a=5^3=6, b=6^3=5, a=6^5=3 ✓

// Array version (in-place):
function swapInArray(arr, i, j) {
    arr[i] ^= arr[j];
    arr[j] ^= arr[i];
    arr[i] ^= arr[j];
}

Time: O(1) | Space: O(1)

There's a pattern based on n % 4: the XOR of 1..n cycles through 4 states. Use this O(1) formula instead of iterating.

function xorUpToN(n) {
    switch (n % 4) {
        case 0: return n;      // 4,8,12... => n itself
        case 1: return 1;      // 1,5,9...  => 1
        case 2: return n + 1;  // 2,6,10... => n+1
        case 3: return 0;      // 3,7,11... => 0
    }
}
// xorRange(l, r) = xorUpToN(r) ^ xorUpToN(l-1)
function xorRange(l, r) { return xorUpToN(r) ^ xorUpToN(l - 1); }

// Input: n=4  => Output: 4   (1^2^3^4=4)
// Input: n=5  => Output: 1   (1^2^3^4^5=1)
// Input: n=6  => Output: 7   (1^2^3^4^5^6=7)
// xorRange(3, 7) = xorUpToN(7)^xorUpToN(2) = 0 ^ 3 = 3

Time: O(1) | Space: O(1)

The sign bit is the MSB (bit 31 in 32-bit integers). XOR the two numbers: if the result's MSB is 1, they have opposite signs.

function oppositeSigns(a, b) {
    return (a ^ b) < 0; // MSB is 1 means different signs
}
// Input: a=4, b=-7   => Output: true
// Input: a=2, b=4    => Output: false
// Input: a=-2, b=-4  => Output: false

// Determine sign of a number:
function isNegative(n) { return (n >>> 31) === 1; }
// Input: -5  => true, 5 => false, 0 => false

Time: O(1) | Space: O(1)

Use n & (-n) to isolate the lowest set bit (returns a power of 2). Take log₂ to find the bit position.

function rightmostSetBit(n) {
    return Math.log2(n & (-n)); // position (0-indexed)
}
// Alternatively, count trailing zeros:
function countTrailingZeros(n) {
    if (n === 0) return 32;
    let pos = 0;
    while ((n & 1) === 0) { n >>>= 1; pos++; }
    return pos;
}
// Input: n=12 (1100)   => Output: position 2  (bit at index 2 is set)
// Input: n=18 (10010)  => Output: position 1  (bit at index 1 is set)
// Input: n=64 (1000000) => Output: position 6

Time: O(log n) for trailing zeros | Space: O(1)

Use DP with the relation: dp[i] = dp[i >> 1] + (i & 1). The count for i equals the count for i/2 (right-shifted) plus the last bit.

function countBits(n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}
// Input: n=5   => Output: [0,1,1,2,1,2]
//   0=0, 1=1, 2=1, 3=2, 4=1, 5=2 (count of 1-bits)
// Input: n=2   => Output: [0,1,1]
// Input: n=0   => Output: [0]

Time: O(n) | Space: O(n)

XOR gives sum without carry. AND << 1 gives carry. Repeat until no carry remains.

function add(a, b) {
    while (b !== 0) {
        const carry = (a & b) << 1; // carry bits
        a = a ^ b;                  // sum without carry
        b = carry;
    }
    return a;
}
// Input: a=1, b=1   => Output: 2
// Input: a=15, b=25 => Output: 40
// Input: a=7, b=8   => Output: 15
// Trace for a=3(011), b=5(101):
//   sum=110=6, carry=001<<1=010=2
//   sum=100=4, carry=010=2 (shifted)...

Time: O(log(max(a,b))) iterations | Space: O(1)

A power of 4 must be: (1) a power of 2 (only one set bit), AND (2) the set bit is at an even position (0, 2, 4...). The mask 0x55555555 has 1s only at even positions.

function isPowerOfFour(n) {
    return n > 0
        && (n & (n - 1)) === 0   // power of 2: exactly one set bit
        && (n & 0x55555555) !== 0; // set bit is at even position
}
// Input: 1    => Output: true  (4^0)
// Input: 16   => Output: true  (4^2)
// Input: 5    => Output: false (not a power of 4)
// Input: 2    => Output: false (power of 2 but not 4)
// 0x55555555 = 01010101...01010101 (even bit positions are 1)

Time: O(1) | Space: O(1)

1What are the AND, OR, and XOR bitwise operators?

2How do left shift and right shift work?

3How do you check if a number is a power of 2?

4How do you count the number of set bits (Hamming Weight)?

5Find the single number using XOR.

6Swap two numbers without a temporary variable.

7How do you toggle the nth bit of a number?

8Find two non-repeating elements in an array where all others repeat twice.

9How do you reverse the bits of an integer?

10How do you generate all subsets using bit manipulation?

11How do you count set bits (Hamming Weight) of a number?

12How do you find the missing number in an array using XOR?

13How do you find two non-repeating numbers in an array where all others appear twice?

14How do you reverse the bits of a 32-bit unsigned integer?

15How do you generate all subsets using bit masking?

16How do you compute the single element in a sorted array where every element appears twice except one?

17How do you swap two numbers without a temporary variable using XOR?

18How do you compute the XOR of integers from 1 to n efficiently?

19How do you check if two integers have opposite signs using bit manipulation?

20How do you find the position of the rightmost set bit?

21How do you compute the number of 1-bits for all numbers from 0 to n?

22How do you add two numbers without using + or - (bit manipulation)?

23How do you check if a number is a power of 4 using bit manipulation?