Bit Manipulation

XOR tricks, bit counting, power-of-2 checks. The handful of bit operations that pop up in interview problems. FIND_VIDEO: search 'bit manipulation tricks interview' — recommended channel: NeetCode / Tushar Roy. Aim for 9 min or under.

6 minutesVideo LessonPDF notes

🎯 Free Guest Mode: You are learning for free. Sign in to save your completion progress and quiz answers.

Loading progress...

Key moments

Missing Number Puzzle — Presents the challenge of finding a missing integer from 1 to a million with zero memory.
Hardware Bitwise Fundamentals — Explains that bitwise operations run directly on CPU hardware in single clock cycles.
Bitmask Construction — Demonstrates creating bitmasks with left shifts to set, clear, and toggle specific bits.
XOR Missing Number Solution — Solves the missing number problem using XOR self-cancellation across expected and actual values.
Brian Kernighan Algorithm — Introduces the n & (n - 1) operation to count set bits in iterations proportional to set bit count.
Power of Two Verification — Explains the constant-time logic for determining whether an integer is a power of two.

PDF notes

Bottom line: You will master fundamental bitwise operations and bitmasking techniques to manipulate raw binary representations directly. You will be able to solve common algorithmic patterns—such as missing number recovery, population count, and power-of-two validation—in O(1) auxiliary space and optimal hardware clock cycles.

This lesson on Bit Manipulation is hands-on and example-driven. You will master fundamental bitwise operations and bitmasking techniques to manipulate raw binary representations directly. You will be able to solve common algorithmic patterns—such as missing number recovery, population count, and power-of-two validation—in O(1) auxiliary space and optimal hardware clock cycles.

What You'll Be Able To Do

Construct bitmasks using left shifts to set, clear, and toggle specific bit positions.
Solve missing number array problems in O(N) time and O(1) space using XOR cancellation properties.
Implement Brian Kernighan's algorithm using the n & (n - 1) identity to count set bits in O(k) time.
Evaluate whether an integer is an exact power of two using a single constant-time bitwise check.

Detailed Concept Walkthrough

1. Bitwise Operators and Bitmasking

Bitwise operators manipulate individual bits in parallel at native CPU speeds. A bitmask acts like a surgical stencil to target and modify specific bit positions without altering surrounding bits.

Mechanism: Create a mask for bit position k by left-shifting 1 by k spots (1 << k). Use bitwise OR (|) to force the bit to 1, bitwise AND with a bitwise NOT (~(1 << k)) to force it to 0, or bitwise XOR (^) to flip it.
Under the Hood: Bitwise logic operations execute directly in the Arithmetic Logic Unit (ALU), typically completing in a single clock cycle with zero memory overhead.
Best Practice: Always isolate the target bit using explicit shifts rather than arithmetic powers of two to ensure predictable constant-time hardware instruction mapping.

# Target the 5th bit (0-indexed)
mask = 1 << 5

# Force bit ON
val_on = num | mask

# Force bit OFF
val_off = num & ~mask

# Toggle bit
val_toggled = num ^ mask

Key Takeaway: Bitmasks use shifts and logic gates to surgically read, set, clear, or toggle bits in O(1) time.

2. XOR Cancellation Properties

XOR returns true only when paired bits differ, creating an identity where any number XORed with itself cancels to zero, and any number XORed with zero remains unchanged.

Mechanism: Because a ^ a = 0 and a ^ 0 = a, identical pairs across an arbitrary sequence of XOR operations neutralize completely regardless of order (commutative and associative).
Execution Flow: To locate a single missing value from 1 to N in an array of size N-1, XOR all expected integers from 1 to N together, then XOR every element present in the array against that cumulative value.
Under the Hood: Matching numbers zero out every bit position simultaneously across the word, leaving only the unpaired value in O(1) extra space.

def find_missing(arr, n):
    xor_sum = 0
    # XOR all expected numbers 1 to n
    for i in range(1, n + 1):
        xor_sum ^= i
    # XOR all present numbers in array
    for num in arr:
        xor_sum ^= num
    return xor_sum  # Only missing number remains

Key Takeaway: Self-cancellation (x ^ x = 0) enables instant filtering of duplicated values without auxiliary memory.

3. Brian Kernighan's Algorithm

Subtracting 1 from a binary number flips the lowest set bit and all trailing zeros, allowing n & (n - 1) to clear exactly one set bit per iteration.

Mechanism: Subtracting 1 inverts the rightmost 1-bit to 0 and changes all following 0s to 1s. Performing a bitwise AND between n and n - 1 clears that lowest 1-bit while leaving higher bits intact.
Under the Hood: Standard bit-counting checks all 32 or 64 bits sequentially; Kernighan's method iterates only k times, where k is the number of active set bits.
Execution Flow: Initialize a counter to 0, execute n = n & (n - 1), increment the counter, and repeat until n becomes 0.

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n - 1)  # Clears the lowest set bit
        count += 1
    return count

Key Takeaway: The expression n & (n - 1) surgically clears the rightmost set bit in each step.

4. Constant Time Power of Two Check

A positive power of two possesses exactly one set bit in binary, meaning its predecessor shares zero overlapping set bits.

Mechanism: For any power of two (e.g., 8 is 1000 in binary), n - 1 flips the leading 1 to 0 and all trailing 0s to 1s (e.g., 7 is 0111). Therefore, n & (n - 1) evaluates to 0.
Syntax Rule: The check requires guarding against zero (n > 0), because 0 is not a power of two despite 0 & -1 evaluating to 0.
Under the Hood: This eliminates loops, divisions, and floating-point logarithms, validating powers of two in a single non-branching cycle.

def is_power_of_two(n):
    # Ensure positive and verify exactly one set bit
    return n > 0 and (n & (n - 1)) == 0

Key Takeaway: A positive integer n is a power of two if and only if n & (n - 1) == 0.

Topics Covered in Bit Manipulation

Missing Number Puzzle (0:00 - 0:45) — Presents the challenge of finding a missing integer from 1 to a million with zero memory.
Hardware Bitwise Fundamentals (0:45 - 1:35) — Explains that bitwise operations run directly on CPU hardware in single clock cycles.
Bitmask Construction (1:35 - 2:30) — Demonstrates creating bitmasks with left shifts to set, clear, and toggle specific bits.
XOR Missing Number Solution (2:30 - 3:30) — Solves the missing number problem using XOR self-cancellation across expected and actual values.
Brian Kernighan Algorithm (3:30 - 4:15) — Introduces the n & (n - 1) operation to count set bits in iterations proportional to set bit count.
Power of Two Verification (4:15 - 5:00) — Explains the constant-time logic for determining whether an integer is a power of two.

DSA for Interviews Cheat Sheet

1 << k — Generates bitmask targeting the k-th bit position
```
mask = 1 << 5
```
n | (1 << k) — Sets the k-th bit to 1
```
n = n | (1 << 3)
```
n & ~(1 << k) — Clears the k-th bit to 0
```
n = n & ~(1 << 3)
```
n ^ (1 << k) — Toggles the k-th bit
```
n = n ^ (1 << 3)
```
n & (n - 1) — Clears the lowest set bit from n
```
n = n & (n - 1)
```
n > 0 and (n & (n - 1)) == 0 — Checks if n is a power of 2
```
is_pow2 = n > 0 and (n & (n - 1)) == 0
```

Comparison Table

Operation	Truth Condition	Primary Utility
AND (&)	Both bits are 1	Clearing bits or checking active flags
OR (	)	Either bit is 1
XOR (^)	Bits are different	Toggling bits and pair cancellation

Common Pitfalls

Mistake: Forgetting to verify n is strictly greater than zero when checking powers of two. Avoid: Prepend the condition with n > 0 before checking n & (n - 1) == 0.
Mistake: Neglecting operator precedence rules when combining bitwise and equality operators. Avoid: Always wrap bitwise expressions in parentheses when comparing results with relational operators.
Mistake: Looping through all fixed word bits (32/64) to count set bits. Avoid: Use Brian Kernighans algorithm to iterate strictly over the count of set bits.

FAQs

Why does XORing identical numbers always produce zero? XOR yields 1 only when bits differ; because identical numbers share identical bits at every position, all bit comparisons evaluate to 0.
Why is Brian Kernighan's algorithm faster than standard bit checking? It clears one set bit per step using n & (n - 1), making iteration count equal to the number of set bits rather than total bit length.
How does n & (n - 1) remove the rightmost set bit? Subtracting 1 turns the lowest 1-bit to 0 and inverts all lower zeros to ones, leaving zero overlapping 1-bits in that lower region when ANDed.

Common pitfalls

Mistake: Forgetting to verify n is strictly greater than zero when checking powers of two. Avoid: Prepend the condition with n > 0 before checking n & (n - 1) == 0.
Mistake: Neglecting operator precedence rules when combining bitwise and equality operators. Avoid: Always wrap bitwise expressions in parentheses when comparing results with relational operators.
Mistake: Looping through all fixed word bits (32/64) to count set bits. Avoid: Use Brian Kernighans algorithm to iterate strictly over the count of set bits.

All right, let's dive in. Today, we're not just looking at code. We're going to peer right under the hood and uncover some of its hidden superpowers. We're talking about bit manipulation, not as some dry academic thing, but as a set of brilliant hacks that let you speak the computer's native language. So, let's see how these simple ones and zeros can pull off some real magic. But first, let me throw a puzzle at you. Imagine you've got an array with a million numbers, from 1 to a million, but one is missing. The catch? You have no extra memory to work with, nothing. How in the world could you find that missing number instantly? It sounds kind of impossible, right? Well, stick around because the answer is way more elegant than you think. The solution to our puzzle, and really, the key to unlocking some serious performance, lies in understanding the code's fastest language. And no, it's not Python or C++. It's the raw, fundamental language of bits. You know, everything we write, every function, every loop, it all gets boiled down into ones and zeros. See, bitwise operations aren't just another programming feature, they are the actual instructions the CPU was built to run. It's the native tongue of the hardware itself. And what's really wild is the speed. Operations like AND, OR, and XOR are often the absolute fastest things a CPU can do. We're talking a single clock cycle sometimes. When you're trying to optimize your code, you literally can't get any faster than that. That's the hardware reality. So, to tap into that speed, we need to know our tools. We've got AND, which is true only if both bits are 1. Pretty simple. Then there's OR, which is true if either bit is 1. And then, we have the star of our show today: XOR, or exclusive OR. It's only true if the bits are different. Simple rules, but unbelievably powerful. So how do we use these? Well, we use something called a bitmask. The best way to think of a bitmask is like a stencil. It's a pattern of bits we create specifically to target and change only the bits we care about, while leaving everything else totally untouched. And here's exactly how that works. Let's say we want to target the fifth bit. First, we make a mask. We just take the number 1 and bit shift it five spots to the left. Boom! We get a number that's all zeros with just one 1 in that fifth position. Now that we have our mask, we can use OR to force that bit on, we can use AND with an inverted mask to force it off, or we can use our friend XOR to just flip it, whatever its current state is. It's like having a set of surgical tools for your data. Okay, now that we have the fundamentals down, let's get back to that impossible puzzle from the beginning. It's time to reveal the first magic trick, and it's powered entirely by XOR. So just to recap: we've got a massive list of numbers, one of them is missing, and we're not allowed to use any extra memory. How do we find it? The whole secret, the absolute key, is this one beautiful property of XOR: if you XOR any number with itself, the result is always zero. Always. Think about it: the bits are identical, so the exclusive OR is false for every single position. They just cancel each other out. And this is the core insight, right? Because X XOR X is zero, and anything XORed with zero is just itself, it means any pair of identical numbers in a long chain of XORs will just vanish. Poof! They have zero impact on the final result. So, here's how we solve the puzzle: you start a variable at zero. First, you XOR it with every number that should be in the list, from 1 all the way to a million. Then, you take that result and you XOR it with every number that's actually in your array. Every number that's in both lists will show up twice, and they'll cancel themselves out. The only number left standing at the end? The one that was missing. It's just brilliant, right? That XOR trick is seriously cool, and it shows you how powerful a single operator can be. Now let's look at another super common problem where a clever bitwise hack just blows the normal solution out of the water: counting the number of ones, or set bits, in a number. Now the slow way is obvious: you just loop through all 32 or 64 bits and check each one. It works, but ugh. The smart way, using Brian Kernighan's algorithm, is to loop only as many times as there are ones. So if a number only has two ones in it, the loop only runs twice, not 64 times. The performance difference can be absolutely massive. So how does this little piece of magic work? The expression n and n minus 1 does something fascinating: it always flips the rightmost 1 bit to a zero, and it leaves all the other bits to its left alone. So every single time you do this operation, you surgically remove one of the ones. You just count how many times you can do it before the number becomes zero. It's so clever. You know, that n and n minus 1 operation is so useful, it's actually the key to our final hack: a ridiculously fast way to check if a number is a power of 2. And you can do it without any loops or division at all. That's it. This single, elegant line of code is all you need. Let's break down the beautiful logic that makes this thing tick. Okay, so a power of 2 in binary is always just a single 1 bit followed by a bunch of zeros. Take the number 8, for example: that's 1000. Now what happens when you subtract 1 from it? That leading 1 flips to a zero, and all the zeros that follow it flip to ones. So 7 is 0111. So, when you AND the original number and the number minus 1, there are zero overlapping ones. The result is just zero. And this is only true for powers of 2. It's foolproof. At the end of the day, these hacks are way more than just clever tricks for coding interviews. They really represent a shift in perspective. It's about thinking about problems not just in terms of loops and variables, but in terms of the raw bits the machine is actually crunching. It's how you write code that's not just correct, but is deeply, mechanically efficient and, well, elegant. And that kind of leaves us with a final thought: by understanding the language of the hardware itself, we find these solutions that are faster and way simpler than we ever would have imagined. It really makes you wonder: what other bits of magic are hiding just below the surface, waiting to be discovered in the simplest lines of your own code?

Frequently asked questions

Why does XORing identical numbers always produce zero?

XOR yields 1 only when bits differ; because identical numbers share identical bits at every position, all bit comparisons evaluate to 0.

Why is Brian Kernighan's algorithm faster than standard bit checking?

It clears one set bit per step using n & (n - 1), making iteration count equal to the number of set bits rather than total bit length.

How does n & (n - 1) remove the rightmost set bit?

Subtracting 1 turns the lowest 1-bit to 0 and inverts all lower zeros to ones, leaving zero overlapping 1-bits in that lower region when ANDed.

How was this lesson?

Your feedback helps us refine explanations and catch bugs.