Bit Manipulation Technique in DSA

Bit Manipulation in a Nutshell

Deals with operations on binary representations of integers.
Uses bitwise operators like AND, OR, XOR, NOT, and bit shifts.
Efficient for solving problems with flags, sets, subsets, parity, and powers of 2.

What is the Bit Manipulation Technique?

Bit Manipulation is a powerful technique in DSA where we use binary operations to solve problems efficiently. It's commonly used in problems related to power-of-two checks, counting bits, generating subsets, toggling bits, and more.

It relies on bitwise operators like:

& (AND)
| (OR)
^ (XOR)
~ (NOT)
<< (left shift)
>> (right shift)

Key Bit Manipulation Operations

1. Check if a Number is a Power of Two — Explained for Beginners

To determine if a number is a power of two using bit manipulation, we rely on the fact that powers of two have a very unique pattern in binary:

1 in binary → 0001
2 in binary → 0010
4 in binary → 0100
8 in binary → 1000

Notice a pattern? Every power of two has exactly one bit set to 1 and all other bits are 0.

This is the key to our trick: if a number n is a power of two, then n has exactly one set bit. And here’s what happens when you subtract 1 from such a number:

n = 8 (binary = 1000)
n - 1 = 7 (binary = 0111)

Now, let’s perform a bitwise AND between n and n - 1:

  1000  (8)
& 0111  (7)
= 0000

The result is 0. This will only happen for numbers that are powers of two.

Step-by-Step Breakdown:

Check if n is greater than 0 (since 0 and negatives are not powers of 2).
Use bitwise AND: n & (n - 1)
If the result is 0, then n is a power of 2. Otherwise, it’s not.

Why Bit Manipulation?

Bit manipulation provides an incredibly fast and elegant solution here. Instead of looping or dividing repeatedly to check powers of 2, we do just one & operation:

Time Complexity: O(1)
Space Complexity: O(1)

This is far more efficient than traditional methods like looping, especially for performance-critical applications like embedded systems, competitive programming, and large-scale simulations.

Pseudocode

// Pseudocode
function isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Examples:

n = 16 → binary = 10000 → n & (n-1) = 10000 & 01111 = 0 → ✅ Power of 2
n = 18 → binary = 10010 → n & (n-1) ≠ 0 → ❌ Not a power of 2

Note: This method only works for positive integers. If n ≤ 0, it's not a power of 2.

2. Count the Number of Set Bits (1s)

Count how many bits are set to 1 in the binary representation of a number.

// Pseudocode
function countSetBits(n):
    count = 0
    while n != 0:
        n = n & (n - 1)
        count += 1
    return count

Explanation: Each iteration clears the rightmost set bit.

3. Toggle a Bit at Position k

Flip the bit at position k (0-based from right).

// Pseudocode
function toggleBit(n, k):
    return n ^ (1 << k)

4. Check if the k-th Bit is Set

Check if bit at position k is 1.

// Pseudocode
function isKthBitSet(n, k):
    return (n & (1 << k)) != 0

5. Turn Off the Rightmost Set Bit

// Pseudocode
function turnOffRightmostBit(n):
    return n & (n - 1)

6. Get the Rightmost Set Bit

// Pseudocode
function getRightmostSetBit(n):
    return n & -n

Explanation: -n is the two's complement of n.

Common Use Cases of Bit Manipulation

Checking if a number is odd or even (n & 1)
Swapping variables without temp (a ^= b; b ^= a; a ^= b)
Generating all subsets of a set
Finding unique element in array where all others appear twice (XOR)

Example: Find the Unique Element

Given an array where every element appears twice except one, find the unique one.

// Pseudocode
function findUnique(arr):
    result = 0
    for num in arr:
        result = result ^ num
    return result

Why it works: XOR cancels out pairs (a ^ a = 0), and 0 ^ b = b.

Time and Space Complexity

Time Complexity: Usually O(1) for individual operations, O(n) for array processing.
Space Complexity: O(1)

Advantages of Bit Manipulation

Extremely fast (hardware-level operations)
Memory-efficient
Elegant for solving subset/flag-based problems

Disadvantages

Harder to read and debug
Tricky for beginners to understand and use safely

Conclusion

Bit Manipulation is an efficient and low-level technique in DSA. It is particularly useful when solving problems related to flags, parity, and optimization. Mastering bit operations can lead to elegant and performant solutions for a variety of tricky problems.