Overview
Every integer is a row of bits, and processors operate on all of them at once. Bitwise operators — AND, OR, XOR, NOT and shifts — let you test, set and clear individual bits in O(1), pack a set of up to 64 flags into one number, and spot patterns that are invisible in decimal.
A few identities do most of the work. x ^ x = 0 and x ^ 0 = x, so XOR-ing a list cancels every pair and leaves the odd one out. x & (x − 1) removes the lowest set bit, so a loop of it counts set bits. And the integers from 0 to 2ⁿ − 1, read as bitmasks, enumerate every subset of n items.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Any single bitwise operation | O(1) |
| Count set bits (Kernighan) | O(number of set bits) |
| Enumerate all subsets of n | O(2ⁿ) |
Patterns to recognise
XOR to cancel pairs
Use it for: Single number, missing number, find the difference.
XOR everything together; duplicates disappear.
Bit-by-bit construction
Use it for: Reverse bits, single number II, sum of two integers.
Process bit positions 0..31 independently and rebuild the answer.
Mask enumeration
Use it for: Subsets, maximum product of word lengths.
Encode each item's properties as a mask; compare with a single AND.
Code template
def single_number(nums):
result = 0
for x in nums:
result ^= x # pairs cancel out
return result
def count_bits(n):
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1)
return bits
int singleNumber(const vector<int>& nums) {
int result = 0;
for (int x : nums) result ^= x; // pairs cancel out
return result;
}
vector<int> countBits(int n) {
vector<int> bits(n + 1, 0);
for (int i = 1; i <= n; ++i) bits[i] = bits[i >> 1] + (i & 1);
return bits;
}
Common mistakes
- Operator precedence: in C++/Java,
x & 1 == 0meansx & (1 == 0)— always parenthesise. - Python integers are unbounded, so negative numbers never "wrap"; mask with 0xFFFFFFFF to emulate 32-bit behaviour.
- Shifting a 32-bit int by 32 or more is undefined in C++; use
1LL << ifor large i.
Quick check
Three questions on Bits. Get all three right to earn +15 XP.
-
What does x & (x - 1) do?
Subtracting 1 flips the lowest 1 and the zeros below it; the AND removes that bit.
-
XOR-ing every number in an array where each value appears twice except one gives:
a ^ a = 0 and a ^ 0 = a, so the pairs cancel.
-
Which expression tests whether x is a power of two?
A power of two has exactly one set bit, so clearing it leaves zero.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Single NumberLeetCode Easy +20
- Number of 1 BitsLeetCode Easy +20
- Counting BitsLeetCode Easy +20
- Reverse BitsLeetCode Easy +20
- Single Number IILeetCode Medium +40
- Sum of Two IntegersLeetCode Medium +40
- Bitwise AND of Numbers RangeLeetCode Medium +40
- Maximum Product of Word LengthsLeetCode Medium +40
Stuck on Bits?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor