What is Bit Manipulation?
Techniques·7 min read·code in python
Bit manipulation is the technique of operating directly on the individual binary digits of integers using bitwise operators, AND, OR, XOR, NOT, and left/right shifts. Instead of treating a number as one value, you read, set, and clear specific bits, enabling fast, memory-light solutions to certain problems.
Think of a number as a row of switches
Every integer is stored as a fixed row of bits, each either 1 (on) or 0 (off). Bit manipulation treats that row as data you can inspect and edit position by position, rather than as a single arithmetic value. Because a CPU runs each of these operations as one hardware instruction, they are about as cheap as computation gets.
The mental model that makes everything else click: a 32-bit integer is 32 tiny switches. Most bit tricks are just clever ways to ask 'which switches are on?' or to flip a chosen switch without touching the others. Watching those switches change one step at a time is far more intuitive than memorizing the identities cold.
The five operators and the idea of a mask
There are only five tools. AND (&) keeps a bit only where both inputs are 1, so it tests or clears bits. OR (|) sets a bit where either input is 1, so it turns bits on. XOR (^) sets a bit where the two differ, so it toggles, and it is self-inverse, meaning a ^ a = 0 and a ^ 0 = a. NOT (~) flips every bit. Shifts (<< and >>) slide bits left or right, which multiplies or divides by powers of two.
A mask is just a purpose-built integer that isolates the bits you care about. The workhorse is 1 << k, a single 1 at position k. With it you can test a bit (x & (1 << k)), set it (x | (1 << k)), clear it (x & ~(1 << k)), or toggle it (x ^ (1 << k)). Almost every bit problem reduces to building the right mask and applying one of these four moves.
The classic patterns interviewers love
Single number: XOR every element of an array together. Equal pairs cancel to 0 and the lone unmatched value survives: one pass, no extra memory. Counting set bits (popcount): Brian Kernighan's trick n &= n - 1 clears the lowest set bit each iteration, so the loop runs exactly once per 1-bit. Power of two: a power of two has exactly one set bit, so n > 0 and (n & (n - 1)) == 0 answers it in one line.
Two more worth knowing: n & -n isolates the lowest set bit, and a bitmask can stand in for a small set of items so you can iterate over all subsets. These few identities cover the large majority of bit-manipulation questions you will actually meet.
The code
def single_number(nums):
# XOR cancels equal pairs; the unique value survives
result = 0
for n in nums:
result ^= n
return result
def count_set_bits(n):
# Brian Kernighan: n & (n - 1) clears the lowest set bit
count = 0
while n:
n &= n - 1
count += 1
return count
def is_power_of_two(n):
# A power of two has exactly one set bit
return n > 0 and (n & (n - 1)) == 0Run it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | Each bitwise or shift operation is O(1). Scanning n numbers (e.g. single number) is O(n); Brian Kernighan's popcount runs in O(number of set bits). |
|---|---|
| Space | O(1) auxiliary: a handful of integer variables, no extra data structures. |
Kernighan's loop is fastest when few bits are set (best case a couple of iterations) and worst case runs once per bit, up to the word width of 32 or 64. A plain bit-by-bit scan is always O(word size) regardless of input.
When to use it
- Tracking a small set of on/off flags compactly: a bitmask instead of a boolean array or hash set, including bitmask DP over subsets.
- A problem hinges on pairing, cancellation, or parity, XOR to find the unique number, spot a missing or duplicated value, or swap two variables without a temp.
- You need fast checks tied to powers of two, testing, setting, or clearing a specific bit, checking if a number is a power of two, or aligning to a boundary.
- Tight memory or performance constraints where replacing arithmetic with shifts and masks genuinely matters (embedded, hashing, low-level systems).
Watch out for
- Operator precedence bites: &, |, and ^ bind looser than == and + in C, Java, JavaScript, and Python, so x & 1 == 0 parses as x & (1 == 0). Always parenthesize the comparison.
- Signed shifts and width surprises: right-shifting negatives, or shifting by more than the type's width, is language-dependent (Java's >> vs >>>, JavaScript coercing to 32 bits, undefined behavior in C). Python ints are arbitrary precision, so ~ and shifts behave differently than fixed-width languages.
- Reaching for bit tricks when they don't help, cleverness that hurts readability without improving complexity. Use them where they truly simplify or are required, not to show off.
Bit Manipulation: questions we get
Is bit manipulation hard to learn?
The operators are simple. There are only five (AND, OR, XOR, NOT, shifts) and each does one clear thing. What takes practice is recognizing when a problem has a bitwise shortcut and building masks fluently. Watching the bits flip step by step makes it click far faster than reading definitions.
When should I use bit manipulation instead of a hash set or array?
Reach for it when you're tracking on/off flags compactly, when a problem relies on XOR's pairing and cancellation, or when you need fast power-of-two checks. For general lookups a hash set is usually clearer. Use bits when they genuinely cut memory or unlock the trick.
What is the time complexity of counting set bits?
Brian Kernighan's method (n &= n - 1) runs once per set bit, so it's O(number of set bits), which is at most the word width of 32 or 64. A naive scan of every bit is O(word size). Both use O(1) extra space.
What does XOR do and why is it useful?
XOR outputs 1 only where two bits differ, and it's self-canceling: a ^ a = 0 and a ^ 0 = a. That makes it ideal for finding a unique element among pairs, toggling bits, detecting differences, and swapping two variables without a temporary.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor