Algorithms
Bit Manipulation (Intro)
Difficulty: Intermediate
Given an array where every element appears twice except one, find the loner. The hash-map solution is O(n) time and O(n) space. XOR-ing every element together solves it in O(n) time and O(1) space, in three lines, exploiting the fact that...
Bit Manipulation (Intro)
Given an array where every element appears twice except one, find the loner. The hash-map solution is O(n) time and O(n) space. XOR-ing every element together solves it in O(n) time and O(1) space, in three lines, exploiting the fact that a ^ a = 0 and a ^ 0 = a. Knowing how integers are laid out as bits unlocks solutions like that across an entire family of problems.
Bit Manipulation (Intro) covers the building blocks. You will master the six bitwise operators (&, |, ^, ~, <<, >>) and the standard tricks: check whether n is a power of two with n & (n - 1) == 0, count set bits, get/set/clear/toggle the ith bit, and the XOR "single number" pattern. The lesson then introduces bitmasks as compact set representations and previews how subset enumeration powers later bitmask DP and TSP algorithms.
In How to Read Code (JS & Python), you saw integers and arithmetic. This lesson zooms in past arithmetic: the same integer is also a fixed-width string of bits you can address one at a time.
Next, Divide and Conquer (Intro) returns to recursion with the recurrence framework that explains merge and quick sort.
Prerequisites:
Algorithms and EfficiencyTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain binary number representation and convert between decimal and binary.
Apply the six bitwise operators (AND, OR, XOR, NOT, left shift, right shift) and describe the effect of each.
Use common bit tricks: check power of 2, count set bits, and get/set/clear/toggle the ith bit.
Solve the 'single number' problem using XOR properties (a ^ a = 0, a ^ 0 = a).
Represent sets as bitmasks and enumerate subsets of a bitmask.
Analyze when bit manipulation provides an advantage over arithmetic approaches.
Why This Matters
01
XOR-based tricks solve 'single number' style problems in O(n) time and O(1) space — a common interview question at top companies.
02
Checking whether a number is a power of 2 with `n & (n - 1) === 0` is a one-liner that replaces loops or logarithms.
03
Bitmasks represent sets as integers, enabling subset enumeration and bitmask DP — essential for competitive programming and NP-hard approximations.
04
Bit manipulation underpins real-world systems: permission flags in Unix, feature toggles, network subnet masks, and low-level graphics programming.
Key Terms
8 terms you'll encounter in this lesson
Bitwise AND (&)
Returns 1 in each bit position where both operands have 1. Used for masking — extracting specific bits from a number.
Bitwise OR (|)
Returns 1 in each bit position where at least one operand has 1. Used for setting bits — turning specific bits on.
Bitwise XOR (^)
Returns 1 in each bit position where exactly one operand has 1. Key properties: a ^ a = 0, a ^ 0 = a. Used for toggling and finding unique elements.
Bitwise NOT (~)
Flips every bit: 0 becomes 1, 1 becomes 0. In two's complement, ~n equals -(n + 1).
Left shift (<<)
Shifts bits left by n positions, filling with zeros. Equivalent to multiplying by 2^n.
Right shift (>>)
Shifts bits right by n positions. Equivalent to integer division by 2^n (for non-negative numbers).
Bitmask
An integer whose binary representation encodes a set. Bit i is 1 if element i is in the set. Enables O(1) set operations via bitwise operators.
Hamming weight
The number of 1-bits in a binary number. Also called the population count or popcount.
Heads Up
Common misconceptions to watch out for
"XOR is the same as OR"
OR returns 1 when either or both bits are 1. XOR returns 1 only when exactly one bit is 1. The key difference: 1 | 1 = 1, but 1 ^ 1 = 0. XOR's self-cancellation property (a ^ a = 0) is what makes it useful for finding unique elements.
"Left shift always doubles the number"
Left shift by 1 doubles the value only when no overflow occurs. In languages with fixed-width integers (like 32-bit int in Java/C++), shifting a large number left can cause overflow. JavaScript uses 32-bit integers for bitwise operations, so 1 << 31 gives a negative number.
"n & (n - 1) removes all set bits"
n & (n - 1) removes only the lowest set bit (rightmost 1). For example, 12 (1100) & 11 (1011) = 8 (1000) — only the rightmost 1 at position 2 was cleared. This is why the trick works for power-of-2 checking: powers of 2 have exactly one set bit.