Bit Manipulation Essentials

1. The Building Blocks: Binary and Bitwise Operators

At the core of bit manipulation is the binary number system. Since you have a computer science degree, you're likely familiar with how integers are represented as a sequence of 0s and 1s. A '1' is a set bit, and a '0' is an unset or cleared bit.

All bitwise operations work on this binary representation. To get started, let's watch a comprehensive video that covers the basics of binary representation, the core bitwise operators (AND, OR, XOR, NOT), and the essential shift operators (<<, >>).

To summarize the key operators:

2. The Core Toolkit: Manipulating the k-th Bit

Most bit manipulation problems boil down to performing an action on a specific bit. To do this, we use the operators we just learned in combination with a mask. A mask is a carefully crafted number that isolates the bit(s) we're interested in. The most common way to create a mask for the k-th bit (from the right, 0-indexed) is 1 << k.

For example, to target the 3rd bit (k=2), our mask would be 1 << 2, which is binary 100.

Let's see how to perform the four fundamental operations. The following video explains the logic, and the article from GeeksforGeeks provides concise code examples in multiple languages you are familiar with.

Now, let's solidify this with code.

Here is a summary of the core operations on the k-th bit of a number num:

• Check if set: (num & (1 << k)) != 0
• Set bit: num = num | (1 << k)
• Clear bit: num = num & ~(1 << k)
• Toggle bit: num = num ^ (1 << k)

3. The Special Properties of XOR

The XOR operator has unique properties that make it a powerful tool for solving certain interview problems elegantly.

Key XOR Properties

1. Identity: x ^ 0 = x
2. Self-inverting: x ^ x = 0
3. Commutative & Associative: x ^ y = y ^ x and (x ^ y) ^ z = x ^ (y ^ z)

These properties lead to some famous applications:

Application 1: Find the Single Unique Number

Problem: You are given an array of integers where every element appears twice, except for one. Find that single one.
Solution: XOR all the numbers in the array together.
Why it works: Let the array be [a, b, a, c, c]. If you XOR them all: (a ^ a) ^ (b) ^ (c ^ c).
Because x ^ x = 0, this simplifies to 0 ^ b ^ 0, which equals b (because x ^ 0 = x). The paired numbers cancel each other out, leaving only the unique number. This is an O(n) time and O(1) space solution.

Application 2: Swap Two Numbers without a Temporary Variable

This is a classic trick that demonstrates a deep understanding of XOR.

The sequence of operations for swapping x and y is:

1. x = x ^ y
2. y = x ^ y // Now y holds the original value of x
3. x = x ^ y // Now x holds the original value of y

4. More Essential Bitwise Patterns for Interviews

To round out your toolkit, here are a few more patterns that are frequently tested.

Checking if a Number is a Power of Two

A number is a power of two if and only if it has exactly one bit set in its binary representation (e.g., 8 is 1000, 16 is 10000).
Consider a number n and n-1:

• n = 8 (00001000)
• n-1 = 7 (00000111)

When you AND them, n & (n-1), the result is 0. This is true for any power of two (except 0).
The check is: n > 0 && (n & (n - 1)) == 0.

This trick is explained well in the "10 Bitwise Tricks" video from 02:39 to 05:06 (resource_id: [LINK](https://www.youtube.com/watch?v=LGrE0siZ-ZA), section 2).

Counting Set Bits (Brian Kernighan's Algorithm)

A naive way to count set bits is to loop 32/64 times and check each bit. A more elegant way is Brian Kernighan's algorithm, which runs in O(k) time where k is the number of set bits.

The core idea is that the operation n = n & (n - 1) clears the rightmost set bit.
By repeatedly applying this operation until the number becomes 0, you can count how many iterations it took. That count is the number of set bits.

Example: n = 12 (1100)

1. n = 12 & 11 => 1100 & 1011 = 1000 (count = 1)
2. n = 8 & 7 => 1000 & 0111 = 0000 (count = 2)
   The number is now 0, so we stop. The number of set bits in 12 is 2.

This powerful technique is covered in the cp-algorithms resource (resource_id: [LINK](https://cp-algorithms.com/algebra/bit-manipulation.html)) under the section "Brian Kernighan's algorithm".

Conclusion

Today we've armed you with a powerful set of low-level optimization tools. While they might seem like niche "tricks," they represent a fundamental way of thinking about data and computation that is highly valued in roles that require deep system understanding.

Key Takeaways:

• Bit manipulation is performed using a core set of operators: &, |, ^, ~, <<, >>.
• Most operations on a specific bit involve the mask-and-operate pattern: create a mask (e.g., 1 << k) and apply the appropriate operator.
• XOR has unique properties (x ^ x = 0, x ^ 0 = x) that enable elegant and efficient solutions for problems like finding the unique element or swapping numbers in-place.
• Common interview patterns like checking for a power of two (n & (n-1)) and counting set bits (Brian Kernighan's algorithm) are essential to have in your arsenal.

This lesson concludes our first module on the foundations of algorithmic analysis. You've rebuilt your core understanding of complexity, recursion, search algorithms, trade-offs, and now, bit manipulation.

In our next lesson, we will begin Module 2: Arrays, Strings, and Pointer Techniques. We'll start with the two-pointer technique, a versatile pattern for solving a wide range of problems on sorted or partitioned arrays.