Bit Manipulation

Bit manipulation is the art of working directly with the binary digits of integers. Operations run in constant time O(1) and use zero extra space — they often replace entire loops. Mastering bit tricks separates good engineers from great ones at the whiteboard.

Binary Representation

Every integer is stored as a sequence of bits (0s and 1s). A 32-bit signed integer uses bit 31 as the sign bit (0 = positive, 1 = negative) and stores negative values using two's complement.

Text

Decimal 13  →  0000 1101
Decimal -1  →  1111 1111  (all bits set in two's complement)

Bit positions (0-indexed from the right):
  bit 3  bit 2  bit 1  bit 0
    1      1      0      1    =  8 + 4 + 0 + 1  =  13

The Six Bitwise Operators

Operator	Symbol	Rule	Example (4-bit)
AND	&	1 only if BOTH bits are 1	1100 & 1010 = 1000
OR	\|	1 if EITHER bit is 1	1100 \| 1010 = 1110
XOR	^	1 if bits are DIFFERENT	1100 ^ 1010 = 0110
NOT	~	Flip every bit (+ sign flip)	~0011 = 1100 = -4
Left Shift	<<	Shift left, fill 0s on right	0011 << 1 = 0110
Right Shift		Shift right, fill with sign bit	1000 >> 1 = 1100

Note

Left shift by k equals multiply by 2^k. Right shift by k equals floor-divide by 2^k. Both are faster than actual multiplication/division on most CPUs.

Essential Bit Tricks Cheat Sheet

Operation	Code	How it works
Check if bit k is set	(n >> k) & 1	Shift bit k to position 0, mask with 1
Set bit k	n \| (1 << k)	OR with a mask that has only bit k set
Clear bit k	n & ~(1 << k)	AND with a mask that has 0 only at bit k
Toggle bit k	n ^ (1 << k)	XOR flips exactly bit k
Clear lowest set bit	n & (n - 1)	Subtracting 1 flips all bits through lowest 1
Isolate lowest set bit	n & (-n)	-n is the two's complement; only LSB survives
Check power of 2	n > 0 && (n & (n-1)) === 0	Powers of 2 have exactly one set bit
Swap without temp	a^=b; b^=a; a^=b	Three-XOR trick

function checkBit(n: number, k: number): boolean {
  return ((n >> k) & 1) === 1;
}
function setBit(n: number, k: number): number {
  return n | (1 << k);
}
function clearBit(n: number, k: number): number {
  return n & ~(1 << k);
}
function toggleBit(n: number, k: number): number {
  return n ^ (1 << k);
}

// n = 13 = 1101
console.log(checkBit(13, 2)); // true   (bit 2 is 1)
console.log(checkBit(13, 1)); // false  (bit 1 is 0)
console.log(setBit(13, 1));   // 15     (1101 | 0010 = 1111)
console.log(clearBit(13, 2)); // 9      (1101 & 1011 = 1001)
console.log(toggleBit(13, 0));// 12     (1101 ^ 0001 = 1100)

XOR Properties — The Magic Operator

a ^ a = 0 — any value XOR itself is zero
a ^ 0 = a — XOR with zero is the identity
Commutative: a ^ b = b ^ a
Associative: (a ^ b) ^ c = a ^ (b ^ c)

These four properties let XOR cancel out duplicate values. XOR all numbers where every element appears twice except one — all pairs reduce to 0, leaving only the unique number.

// LeetCode 136 — Single Number   O(n) time · O(1) space
function singleNumber(nums: number[]): number {
  let result = 0;
  for (const n of nums) {
    result ^= n;   // duplicate pairs cancel: a ^ a = 0
  }
  return result;
}

// [2, 3, 2, 4, 3]  →  0^2^3^2^4^3
//   = (2^2) ^ (3^3) ^ 4  =  0 ^ 0 ^ 4  =  4
console.log(singleNumber([2, 3, 2, 4, 3]));  // 4

Count Set Bits — Brian Kernighan's Algorithm

The naive approach loops all 32 bit positions. Kernighan's trick loops only as many times as there are set bits by repeatedly clearing the lowest set bit with n & (n - 1).

// O(number of set bits) — far faster than O(32) for sparse integers
function countSetBits(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1);  // clears the lowest set bit
    count++;
  }
  return count;
}

// Trace for n = 13 (1101):
//   1101 & 1100 = 1100  count = 1
//   1100 & 1011 = 1000  count = 2
//   1000 & 0111 = 0000  count = 3  done
console.log(countSetBits(13)); // 3

Find the Missing Number

Given an array of n distinct numbers in range [0, n], find the one missing. XOR every index with every value — all present numbers cancel, leaving the missing index.

// LeetCode 268 — Missing Number   O(n) time · O(1) space
function missingNumber(nums: number[]): number {
  let xor = nums.length;        // start with n (last expected value)
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i];         // XOR current index and current value
  }
  return xor;
}

// [3, 0, 1]   n = 3
// xor = 3 ^ (0^3) ^ (1^0) ^ (2^1)
//     = 3 ^ 3 ^ 0 ^ 1 ^ 0 ^ 2 ^ 1
//     = 0 ^ 0 ^ 0 ^ 2  =  2
console.log(missingNumber([3, 0, 1])); // 2

Check Power of Two

// Powers of 2 in binary:  1, 10, 100, 1000, ...  (exactly one 1-bit)
// n - 1 for a power of 2:     0, 01, 011, 0111, ...  (all bits below flipped)
// AND result is always 0 for powers of 2

function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}

// 16 = 10000,  15 = 01111  → AND = 00000  ✓
// 12 = 01100,  11 = 01011  → AND = 01000  ✗
console.log(isPowerOfTwo(16)); // true
console.log(isPowerOfTwo(12)); // false

Reverse Bits

// LeetCode 190 — Reverse Bits
// Read LSB of n, write to MSB of result, repeat 32 times
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
  }
  return result >>> 0;  // ensure unsigned 32-bit return
}

// 00000010100101000001111010011100 → 964176192
console.log(reverseBits(43261596)); // 964176192

Swap Without a Temporary Variable

// Three-XOR swap (no temp needed)
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];
}

console.log(swapBits(5, 9)); // [9, 5]

Warning

XOR swap breaks when both variables point to the same memory location (e.g. swapping arr[i] with itself). Always guard with i !== j before using this in-place.

Common Interview Problems at a Glance

Problem	Key Insight	Complexity
Single Number (LC 136)	XOR all — pairs cancel to 0	O(n) / O(1)
Missing Number (LC 268)	XOR indices and values together	O(n) / O(1)
Reverse Bits (LC 190)	Extract LSB, build result 32 times	O(32) / O(1)
Number of 1 Bits (LC 191)	Brian Kernighan: n &= n-1 per iteration	O(k) / O(1)
Power of Two (LC 231)	n & (n-1) === 0	O(1) / O(1)
Sum of Two Integers (LC 371)	a^b = sum without carry; (a&b)<<1 = carry	O(1) / O(1)
Single Number III (LC 260)	XOR all, split by differing bit, XOR again	O(n) / O(1)

Tip

When you see "find the odd one out," "detect duplicate," or "O(1) space with cancellation" — reach for XOR first. When you see "divisible by power of 2" — use bitwise AND instead of modulo for speed.