Bit manipulation - DSA Learning Guide

Overview

Bit manipulation works directly on the binary representation of integers using AND (&), OR (|), XOR (^), NOT (~), and shifts (<<, >>). These operations run in a single CPU instruction, so they are extremely fast and let you pack many booleans into one integer.

A small set of identities solves a large family of problems: x ^ x = 0 and x ^ 0 = x (find the unique element), x & (x - 1) clears the lowest set bit (count bits, power of two), x & -x isolates the lowest set bit, and a bitmask of n bits represents a subset of n items.

A row of light switches

An integer is a row of 32 switches. AND with a mask checks whether chosen switches are on, OR turns switches on, XOR flips them, and shifting slides the whole row left or right.

When to use it

Find the element that appears an odd number of times, or missing numbers.
Check, set, clear, or toggle individual flags.
Count set bits, test powers of two.
Represent subsets of up to about 20 to 30 items (bitmask enumeration or DP).
Arithmetic without + or * (add with XOR and carry).

Problem patterns it solves

XOR cancellation

Recognize it when: every value appears twice except one; missing number.

136. Single Number
268. Missing Number
389. Find the Difference
1720. Decode XORed Array

Count and clear set bits

Recognize it when: number of 1 bits, power of two, bit counts for 0..n.

191. Number of 1 Bits
231. Power of Two
338. Counting Bits
461. Hamming Distance

Bit-by-bit construction

Recognize it when: reverse bits, count bits per position, single number with triples.

190. Reverse Bits
137. Single Number II
477. Total Hamming Distance

Split by a differing bit

Recognize it when: two unique numbers among pairs.

260. Single Number III

Bitmask subsets and DP

Recognize it when: n <= 20: subsets as integers, DP over masks.

78. Subsets
1239. Maximum Length of a Concatenated String with Unique Characters
847. Shortest Path Visiting All Nodes
526. Beautiful Arrangement

Arithmetic with bits

Recognize it when: add or divide without operators.

371. Sum of Two Integers
29. Divide Two Integers

Where it is used in real software

Permissions and flags

Unix file permissions (rwx = 4 + 2 + 1), feature flags, and enum sets (Java EnumSet) are bit fields.

Networking

Subnet masks compute network addresses with IP & mask; protocols pack header flags into bits.

Bloom filters and bitmap indexes

Databases and caches use bit arrays for fast set membership and filtering.

Graphics and games

Color channels are extracted with shifts and masks; chess engines represent the board as 64-bit bitboards.

Key terms

AND &: 1 only if both bits are 1; used to test and clear bits.
OR |: 1 if either bit is 1; used to set bits.
XOR ^: 1 if the bits differ; x ^ x = 0, x ^ 0 = x.
Two's complement: Negative numbers: invert all bits and add 1; -x = ~x + 1.
>> vs >>>: Arithmetic shift keeps the sign; unsigned shift (>>> in JS/Java) fills with 0.

Core tricks

1
Check bit i
(x >> i) & 1, or (x & (1 << i)) !== 0.
2
Set / clear / toggle bit i
x | (1 << i), x & ~(1 << i), x ^ (1 << i).
3
Clear the lowest set bit
x & (x - 1). Repeating it counts set bits (Brian Kernighan's algorithm).
4
Isolate the lowest set bit
x & -x. Used in Fenwick trees and Single Number III.
5
Power of two
x > 0 && (x & (x - 1)) === 0: exactly one bit is set.

Operations on 13 and 7

13 = 1101, 7 = 0111

Expression	Binary	Result	Meaning
13 & 7	0101	5	bits set in both
13 \| 7	1111	15	bits set in either
13 ^ 7	1010	10	bits that differ
13 & 12 (x & (x - 1))	1100	12	lowest set bit cleared
13 & -13	0001	1	lowest set bit isolated
13 >> 1	0110	6	divide by 2
13 << 1	11010	26	multiply by 2

NOWExpression: 13 & 7 | Binary: 0101 | Result: 5 | Meaning: bits set in both

These seven operations cover most interview bit problems. For example, XOR of [4, 1, 2, 1, 2] = 4 because every pair cancels to 0.

Implementation

1const singleNumber = (nums) => nums.reduce((acc, x) => acc ^ x, 0);2 3function hammingWeight(n) {4  let count = 0;5  while (n !== 0) {6    n &= n - 1; // clear lowest set bit7    count++;8  }9  return count;10}11 12// 338. Counting Bits: bits(i) = bits(i >> 1) + (i & 1)13function countBits(n) {14  const bits = new Array(n + 1).fill(0);15  for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);16  return bits;17}18 19// 268. Missing Number: XOR indexes and values20function missingNumber(nums) {21  let x = nums.length;22  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];23  return x;24}25 26// 260. Single Number III: split by a bit where the two answers differ27function singleNumberIII(nums) {28  const xor = nums.reduce((a, b) => a ^ b, 0);29  const diffBit = xor & -xor;30  let a = 0;31  for (const x of nums) if (x & diffBit) a ^= x;32  return [a, xor ^ a];33}34 35// JS bitwise ops use 32-bit signed ints: use >>> 0 for unsigned results36function reverseBits(n) {37  let result = 0;38  for (let i = 0; i < 32; i++) {39    result = (result << 1) | (n & 1);40    n >>>= 1;41  }42  return result >>> 0;43}

Complexity and performance

Single bit operationO(1)

One CPU instruction.

Count bits (Kernighan)O(set bits)

At most 32 or 64 iterations.

Per-bit loopO(32 x n)

Single Number II style.

Bitmask enumerationO(2^n)

All subsets of n items.

Trade-offs

Speed vs readability

Bit tricks are fast but cryptic; name helper functions (isPowerOfTwo, lowBit) and comment the identity used.

Language limits

JavaScript bitwise operators work on 32-bit signed integers; use BigInt or Math for larger values. Java has int (32) and long (64).

Variants and related techniques

Bitmask DP

dp[mask] over subsets of visited nodes solves TSP-like problems for n <= 20.

Gray code

i ^ (i >> 1) gives sequences where consecutive values differ by one bit.

Binary trie

Maximum XOR pair problems insert numbers bit by bit into a trie.

Common mistakes

Operator precedence.
Fix: x & 1 === 0 parses as x & (1 === 0). Always parenthesize: (x & 1) === 0.
Negative numbers with >>.
Fix: Arithmetic shift keeps the sign bit; loops on negative n with >> never reach 0. Use >>> for unsigned behavior.
1 << 31 overflow.
Fix: In Java and JS it becomes negative; use 1L << 31 in Java.

Interview questions

Why does x & (x - 1) remove the lowest set bit?

Subtracting 1 flips the lowest set bit to 0 and all lower zero bits to 1. ANDing with the original clears exactly that bit and leaves higher bits unchanged.

How do you find the single number when every other appears twice?

XOR all numbers. Pairs cancel because a ^ a = 0, and XOR is commutative, so only the unique number remains. O(n) time, O(1) space.

Practice problems

Problem	Difficulty	What it trains
136. Single Number	Easy	XOR cancellation.
191. Number of 1 Bits	Easy	Kernighan's trick.
338. Counting Bits	Easy	DP with shifts.
268. Missing Number	Easy	XOR indexes.
137. Single Number II	Medium	Per-bit counting.
260. Single Number III	Medium	Split by lowest set bit.
371. Sum of Two Integers	Medium	Carry with AND and shift.