Bits and Pieces: Essential Bit Manipulation Techniques
Unraveling the Magic of Binary Tricks for Smarter Code
Bit manipulation always felt like a mysterious art to me—a combination of math, binary, and low-level magic. When I started diving deeper into Data Structures and Algorithms (DSA), I realized how powerful these techniques could be for solving complex problems efficiently. Here’s a collection of essential techniques and insights I discovered along the way.
Understanding Numbers at the Bit Level
Even or Odd?
Even Number: Its least significant bit (LSB) is 0.
( n & 1 = 0 )Odd Number: Its least significant bit (LSB) is 1.
( n & 1 = 1 )
What Happens When Subtracting 1?
When you subtract 1 from a number:
All bits after the rightmost set bit, including the set bit itself, are flipped.
Example 1: n = 12 (Binary: 1100)
Subtract 1: n - 1 = 11 (Binary: 1011)
Explanation: The rightmost set bit (1) and all bits to the right of it are flipped: 1100 becomes 1011.
Example 2: n = 7 (Binary: 0111)
Subtract 1: n - 1 = 6 (Binary: 0110)
Explanation: The rightmost set bit (1) and all bits to the right of it are flipped: 0111 becomes 0110.
Implications:
[ n & (n - 1) ]
This operation clears the rightmost set bit.
Example:
For n = 12 (binary: 1100)
n - 1 = 11(binary: 1011)( n & (n - 1) ) = 1100 & 1011 = 1000
Power of 2
A number is a power of 2 if and only if it has exactly one bit set in its binary representation (e.g., 1, 2, 4, 8, 16, …)
Check if a number is a power of 2:
[ n & (n - 1) == 0 ]
Why does this work? → Subtracting 1 flips all the bits after the rightmost set bit, including the bit itself. Performing ( n & (n - 1) ) clears this set bit, resulting in zero if there was only one bit set initially.
It also implies that when we write a number n in binary, its least significant bit (rightmost 1) represents the smallest power of 2 that divides it.
Example:
For n = 12 (which is
1100in binary), the least significant 1 is at the second position, which corresponds to2^2.For n = 6 (which is
0110in binary), the least significant 1 is at the first position, corresponding to2^1.For n = 7 (which is
0111in binary), the least significant 1 is at the zero position, corresponding to2^0.
Note: The operation ( n & (n - 1) ) exploits the same bit-flipping nature of subtraction as presented above.
Multiplication and Division by Powers of 2
Efficiently multiply or divide numbers using bit shifting:
Multiply:
n « k(shifts bits to the left by k ) — equivalent ton * 2^k.Divide:
n » k(shifts bits to the right by k ) — equivalent ton / 2^k.
Negative Numbers & Two’s Complement
In computer systems, negative numbers are represented using two’s complement notation. This approach simplifies arithmetic operations and ensures that addition, subtraction, and bitwise operations work seamlessly across positive and negative integers.
How Two’s Complement Works:
To find the two’s complement of a number:
Start with the binary representation of the number’s absolute value.
Invert all the bits (flip 0s to 1s and 1s to 0s).
Add 1 to the result.
Mental Model of Two’s Complement
Start from the least significant bit (LSB).
Keep the bits unchanged until the first 1 is encountered.
After encountering the first 1, flip all remaining bits.
The Most Significant Bit (MSB) Represents the Sign:
0: The number is non-negative (positive or zero).
1: The number is negative.
Implications
This operation isolates the rightmost set bit of:
[ n & -n ]
Example 1:
For n = 6 (binary: 0110),
(two’s complement of 0110) →
1010n & -n = 0110 & 1010 = 0010
Example 2:
For n = 7 (binary: 0111),
(two’s complement of 0111) → 1001
n & -n = 0111 & 1001 = 0001
This can be visualized as the smallest power of 2 that divides n.
XOR: The “Difference Detector”
The XOR operator (^) compares each bit of two numbers:
If the bits are different, the result is 1.
If the bits are the same, the result is 0.
Implications of XOR
a ^ a = 0: XORing a number with itself results in 0.a ^ 0 = a: XORing a number with 0 leaves it unchanged.a ^ b < 0: This is true if a and b have opposite signs.
Swapping Two Numbers Without a Temporary Variable
Using XOR, you can swap two numbers in three steps:
a = a ^ bb = a ^ bis equivalent tob = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = aa = a ^ bis equivalent toa = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b
Example:
For a = 5 (0101) and b = 3 (0011):
1. a = 0101 ^ 0011 = 0110
2. b = 0110 ^ 0011 = 0101
3. a = 0110 ^ 0101 = 0011
Now a = 3 and b = 5 . Magic, no temporary variable required!
Conclusion
Bit manipulation is a cornerstone of efficient algorithms and problem-solving. Whether it’s for toggling bits, isolating flags, or performing quick calculations, these techniques can transform how you approach challenges in Data Structures and Algorithms (DSA) and low-level programming.
What’s your favorite bit manipulation trick? Share it in the comments!