Bit Manipulation

Binary representation

Every integer in a computer is stored as a fixed sequence of bits (0s and 1s).

Unsigned integers: value = sum of 2^i for each bit i that is set.

13 = 8 + 4 + 1
   = 2³ + 2² + 2⁰
   = 1101 in binary

Two’s complement (signed integers): The most significant bit (MSB) is the sign bit — 0 means non-negative, 1 means negative. To negate any number: flip all bits, then add 1.

 5 in 8-bit:  00000101
-5 in 8-bit:  11111011   (flip: 11111010, add 1: 11111011)

Key consequences you must know cold:

• -1 is all 1-bits: 11111111 11111111 11111111 11111111 (32-bit)
• ~n = -(n + 1) — flipping all bits of n gives -n - 1 (two’s complement identity)
• For 32-bit signed integers: range is -2,147,483,648 to 2,147,483,647
• JavaScript bitwise operations convert all operands to 32-bit signed integers before operating

Bitwise operators

AND (&)

Both bits must be 1 for the result bit to be 1. Used to mask (extract) specific bits.

// Check if bit i is set
function isBitSet(n: number, i: number): boolean {
  return (n & (1 << i)) !== 0
}

// Isolate the lower k bits
function lowerKBits(n: number, k: number): number {
  return n & ((1 << k) - 1)
}

console.log(6 & 3)    // 110 & 011 = 010 = 2
console.log(12 & 10)  // 1100 & 1010 = 1000 = 8

OR (|)

At least one bit must be 1. Used to set specific bits.

function setBit(n: number, i: number): number {
  return n | (1 << i)
}

console.log(6 | 3)    // 110 | 011 = 111 = 7
console.log(12 | 10)  // 1100 | 1010 = 1110 = 14

XOR (^)

Bits differ → 1. Bits same → 0. Key algebraic properties:

• a ^ a = 0 (self-inverse: XOR with itself cancels out)
• a ^ 0 = a (identity: XOR with 0 is a no-op)
• Commutative and associative

function toggleBit(n: number, i: number): number {
  return n ^ (1 << i)
}

console.log(6 ^ 3)  // 110 ^ 011 = 101 = 5
console.log(5 ^ 5)  // 0   (self-cancelling)
console.log(5 ^ 0)  // 5   (identity)
console.log(7 ^ 3 ^ 3)  // 7  (3 cancels itself)

XOR is the foundation of three important tricks: finding the unique element among duplicates, swapping without a temp, and checking bit differences.

NOT (~)

Flips all bits. In two’s complement: ~n === -(n + 1).

console.log(~5)    // -6
console.log(~0)    // -1
console.log(~(-1)) // 0

Left shift (<<)

Shifts bits left by the given amount, filling with 0s on the right. Each position left multiplies by 2.

console.log(1 << 3)  // 8   (1 × 2³)
console.log(3 << 2)  // 12  (3 × 4)
console.log(1 << 31) // -2147483648  ← sets the sign bit in 32-bit signed!

Arithmetic right shift (>>)

Shifts bits right, preserving the sign bit (fills left with the sign bit). Each position right divides by 2 (truncated).

console.log(8 >> 1)    //  4  (positive: fills with 0s)
console.log(-8 >> 1)   // -4  (negative: fills with 1s, sign preserved)
console.log(7 >> 1)    //  3  (truncates toward negative infinity)

Unsigned right shift (>>>)

JavaScript-specific: shifts right and fills with 0s regardless of sign. Treats the value as unsigned.

console.log(-1 >>> 0)   // 4294967295  (all 32 bits set, unsigned interpretation)
console.log(-8 >>> 1)   // 2147483644  (not -4!)
console.log(8 >>> 1)    // 4           (same as >> for positive numbers)

Use >>> 0 to convert a potentially negative 32-bit value to its unsigned equivalent.

Essential tricks

These patterns appear constantly — know them by heart.

// 1. Check if n is a power of 2
//    Powers of 2 have exactly one set bit: 1000...0
//    n-1 flips all lower bits:             0111...1
//    AND of the two is always 0
function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0
}

// 2. Isolate the lowest set bit
//    -n in two's complement flips all bits then adds 1,
//    which preserves only the lowest set bit
function lowestSetBit(n: number): number {
  return n & (-n)
}

// 3. Clear the lowest set bit — the heart of Brian Kernighan's algorithm
//    n-1 turns the lowest set bit to 0 and flips all lower bits to 1
//    AND with n clears exactly that one bit
function clearLowestSetBit(n: number): number {
  return n & (n - 1)
}

// 4. Count set bits — Brian Kernighan's algorithm
//    Each iteration clears one set bit. Runs in O(k) where k = set bit count.
//    Faster than looping over all 32 positions when bits are sparse.
function countSetBits(n: number): number {
  let count = 0
  while (n !== 0) {
    n = n & (n - 1)
    count++
  }
  return count
}

// 5. Swap two numbers without a temporary variable
function swapBits(a: number, b: number): [number, number] {
  a ^= b        // a = a XOR b
  b ^= a        // b = b XOR (a XOR b) = original a
  a ^= b        // a = (a XOR b) XOR original a = original b
  return [a, b]
}

// 6. Sign of a number (without branching)
function sign(n: number): number {
  return 1 | (n >> 31)  // 1 for positive/zero, -1 for negative
}

Single Number — LC 136

Every element in the array appears exactly twice except for one. Find the single element in O(n) time and O(1) space.

Trick: XOR all elements. Duplicate pairs cancel each other out (a ^ a = 0), leaving only the unique element.

function singleNumber(nums: number[]): number {
  return nums.reduce((xor, n) => xor ^ n, 0)
}

// [2, 2, 1] → 0 ^ 2 ^ 2 ^ 1 = 0 ^ 0 ^ 1 = 1
// [4, 1, 2, 1, 2] → 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

Time: O(n). Space: O(1). No hash map needed.

Single Number II — LC 137

Every element appears exactly three times except for one. Find the single element.

Trick: For each bit position, count how many numbers have that bit set. If the count mod 3 is 1, the unique number has that bit set. If 0, it does not.

function singleNumberII(nums: number[]): number {
  let result = 0
  for (let i = 0; i < 32; i++) {
    let bitSum = 0
    for (const num of nums) {
      bitSum += (num >> i) & 1
    }
    if (bitSum % 3 === 1) {
      result |= (1 << i)
    }
  }
  return result | 0  // force 32-bit signed interpretation
}

Optimized O(1) space — bit automaton approach:

Track which bits have been seen once (ones) and twice (twos). When a bit is seen a third time, it drops out of both.

function singleNumberIIOptimal(nums: number[]): number {
  let ones = 0, twos = 0
  for (const num of nums) {
    ones = (ones ^ num) & ~twos  // add to ones only if not already in twos
    twos = (twos ^ num) & ~ones  // add to twos only if not already in ones
  }
  return ones  // ones holds bits seen exactly once
}

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

Number of 1 Bits — LC 191

Count the number of set bits (Hamming weight) in a 32-bit unsigned integer.

function hammingWeight(n: number): number {
  n = n >>> 0  // treat as unsigned 32-bit to handle negative input safely
  let count = 0
  while (n !== 0) {
    n = n & (n - 1)  // clear the lowest set bit
    count++
  }
  return count
}

// Trace for n = 11 (binary 1011):
// 1011 → 1010 → 1000 → 0000  (3 iterations = 3 set bits)

Time: O(k) where k = number of set bits. Space: O(1).

Note: The naive approach loops over all 32 bit positions — O(32). Brian Kernighan’s algorithm only iterates over set bits, making it faster for sparse integers.

Counting Bits — LC 338

Return an array ans where ans[i] = number of set bits in i, for all 0 <= i <= n.

Trick: i >> 1 is i with its last bit removed (already computed). Adding i & 1 accounts for the last bit.

function countBits(n: number): number[] {
  const dp = new Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1)
    //       ^^^^^^^^^^^  ^^^^^^^^
    //       bits in i/2  last bit of i (0 if even, 1 if odd)
  }
  return dp
}

// n = 5: [0, 1, 1, 2, 1, 2]
// i=4 (100): dp[2] + 0 = 1 + 0 = 1  ✓
// i=5 (101): dp[2] + 1 = 1 + 1 = 2  ✓

Time: O(n). Space: O(n). This is DP with a bit trick. The naive approach calling hammingWeight(i) for each i would be O(n × 32) = O(n log n).

Reverse Bits — LC 190

Reverse the bits of a 32-bit unsigned integer.

function reverseBits(n: number): number {
  let result = 0
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1)  // shift result left, append LSB of n
    n >>>= 1                           // unsigned right shift n (zero-fills MSB)
  }
  return result >>> 0  // ensure unsigned 32-bit result
}

// For n = 43261596 (00000010100101000001111010011100):
// Result  = 964176192 (00111001011110000010100101000000)

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

result >>> 0 is critical: without it, if bit 31 of result is set, JavaScript’s signed integer representation returns a negative number, which is wrong for an unsigned reverse.

Missing Number — LC 268

Given an array containing n distinct numbers in the range [0, n], find the one that’s missing.

function missingNumber(nums: number[]): number {
  const n = nums.length
  // XOR all indices 0..n with all values in nums
  // Each present number cancels with its index; only the missing number survives
  let xor = n
  for (let i = 0; i < n; i++) {
    xor ^= i ^ nums[i]
  }
  return xor
}

// nums = [3, 0, 1], n = 3
// xor = 3 ^ (0^3) ^ (1^0) ^ (2^1) = 3^3^0^1^2^1 = 0^0^2 = 2  ✓

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

Sum of Two Integers — LC 371

Add two integers without using + or -.

Trick: XOR gives the sum without carries. AND shifted left gives the carry bits. Repeat until there are no more carries.

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1  // positions where both bits are 1 produce a carry
    a = a ^ b                    // sum without carry
    b = carry                    // carry propagates to next position
  }
  return a
}

// 3 + 5:
// Round 1: carry = (011 & 101) << 1 = 001 << 1 = 010
//          a     = 011 ^ 101 = 110
//          b     = 010
// Round 2: carry = (110 & 010) << 1 = 010 << 1 = 100
//          a     = 110 ^ 010 = 100
//          b     = 100
// Round 3: carry = (100 & 100) << 1 = 1000
//          a     = 100 ^ 100 = 000
//          b     = 1000
// Round 4: carry = (000 & 1000) << 1 = 0
//          a     = 000 ^ 1000 = 1000 = 8  ✓

Time: O(1) — at most 32 iterations. Space: O(1).

Handles negative numbers correctly: two’s complement arithmetic works the same way for XOR/AND operations, so the algorithm is correct for all 32-bit integers.

Maximum XOR of Two Numbers in an Array — LC 421

Find the maximum XOR of any two numbers in nums.

Trie approach: Insert all numbers into a binary trie (MSB first). For each number, greedily walk the trie choosing the opposite bit at each level — opposite bits XOR to 1, maximizing the result.

class TrieNode {
  children: (TrieNode | null)[] = [null, null]
}

function findMaximumXOR(nums: number[]): number {
  const root = new TrieNode()

  function insert(num: number): void {
    let node = root
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1
      if (!node.children[bit]) node.children[bit] = new TrieNode()
      node = node.children[bit]!
    }
  }

  // For each number, find the max XOR achievable against the trie
  function query(num: number): number {
    let node = root, xor = 0
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1
      const want = 1 - bit  // prefer opposite bit to get a 1 in XOR result
      if (node.children[want]) {
        xor |= (1 << i)
        node = node.children[want]!
      } else {
        node = node.children[bit]!
      }
    }
    return xor
  }

  for (const num of nums) insert(num)
  return nums.reduce((max, num) => Math.max(max, query(num)), 0)
}

Time: O(n × 32) = O(n). Space: O(n × 32) for the trie.

Bitmask DP

Use an integer as a compact representation of a set: bit i is 1 if element i is in the set, 0 otherwise. State space becomes 2^n subsets.

When to use: n is small (typically n ≤ 20 or n ≤ 25). Problems over all subsets: assignment problems, TSP variants, minimum cost covering all states.

Essential bitmask operations:

const n = 4

// All elements included: (1 << n) - 1
const fullMask = (1 << n) - 1  // 1111 = 15

// Check if element i is in mask
const has = (mask: number, i: number) => (mask & (1 << i)) !== 0

// Add element i to mask
const add = (mask: number, i: number) => mask | (1 << i)

// Remove element i from mask
const remove = (mask: number, i: number) => mask & ~(1 << i)

// Iterate over all subsets of mask (excluding empty set)
function iterateSubsets(mask: number): void {
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process subset `sub`
  }
}

// Popcount (number of set bits)
function popcount(mask: number): number {
  let count = 0
  let m = mask
  while (m !== 0) { m &= m - 1; count++ }
  return count
}

TSP-style example — Traveling Salesman Problem:

// dp[mask][i] = min cost to visit exactly the cities in mask, ending at city i
function tsp(cost: number[][]): number {
  const n = cost.length
  const full = (1 << n) - 1
  const INF = Infinity
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array(n).fill(INF)
  )
  dp[1][0] = 0  // start at city 0, mask = 0001

  for (let mask = 1; mask <= full; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue   // u not in current mask
      if (dp[mask][u] === INF) continue
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue    // v already visited
        const nextMask = mask | (1 << v)
        dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + cost[u][v])
      }
    }
  }

  // Return to starting city 0
  let ans = INF
  for (let u = 1; u < n; u++) {
    if (dp[full][u] !== INF) ans = Math.min(ans, dp[full][u] + cost[u][0])
  }
  return ans
}

Time: O(2^n × n²). Space: O(2^n × n). Feasible for n ≤ 20.

JavaScript gotcha: 32-bit signed integers

JavaScript’s bitwise operators always convert operands to 32-bit signed integers before operating and return a 32-bit signed integer. This causes surprises.

// Shift amount is taken mod 32 — shifting by 32 is a no-op!
console.log(1 << 32)    // 1  (not 0)
console.log(1 << 31)    // -2147483648  (sets sign bit → negative)

// >>> 0 converts to unsigned 32-bit
console.log(-1 >>> 0)           // 4294967295
console.log(0x80000000 | 0)     // -2147483648  (MSB set = negative in signed)
console.log(0x80000000 >>> 0)   // 2147483648   (correct unsigned value)

// XOR with all 1s flips every bit (equivalent to bitwise NOT for unsigned)
const unsignedFlip = (n: number) => (n ^ 0xFFFFFFFF) >>> 0

// Safe popcount for potentially negative inputs
function hammingWeightSafe(n: number): number {
  n = n >>> 0   // reinterpret as unsigned 32-bit before counting
  let count = 0
  while (n !== 0) { n = n & (n - 1); count++ }
  return count
}

Rules of thumb:

• Use >>> 0 any time you need unsigned 32-bit semantics
• Avoid 1 << 31 in arithmetic — it produces a negative 32-bit signed integer
• Bit shifts with amounts ≥ 32 silently wrap (shift amount % 32)
• Use BigInt when you genuinely need more than 31 usable bits

Complexity and use-case reference