Understanding Bit Manipulation

Introduction

Bit Manipulation is a technique that involves working directly with the binary representation of numbers. It is extremely fast and powerful, often used for optimization, cryptography, competitive programming, graphics, compression, and system-level programming.

This chapter will teach you how to use bitwise operators efficiently to solve complex problems in just a few operations.

What Are Bits?

A bit is the smallest unit of data in a computer: 0 or 1.

Every number is stored as a combination of bits:

5 ? 0101
7 ? 0111

Bit manipulation allows you to work with these bits directly.

Bitwise Operators

These are the most commonly used operators:

1. AND (&)

1 & 1 = 1
1 & 0 = 0

Useful for masking bits.

2. OR (|)

1 | 0 = 1

Sets a bit.

3. XOR (^)

1 ^ 1 = 0
1 ^ 0 = 1

Useful for toggling or finding unique numbers.

4. NOT (~)

Flips bits.

~1 = 0

5. Left Shift (<<)

5 << 1 ? 10

Equivalent to multiplying by 2.

6. Right Shift (>>)

10 >> 1 ? 5

Equivalent to dividing by 2.

Useful Bit Manipulation Tricks

1. Check if a number is even or odd

if ((n & 1) == 0)
    Console.WriteLine("Even");

2. Swap two numbers without a temporary variable

a = a ^ b;
b = a ^ b;
a = a ^ b;

3. Count set bits (1s in binary form)

int CountBits(int n)
{
    int count = 0;
    while (n > 0)
    {
        count += (n & 1);
        n >>= 1;
    }
    return count;
}

4. Check if a number is a power of 2

bool IsPowerOfTwo(int n)
{
    return (n > 0) && ((n & (n - 1)) == 0);
}

Example:

8 ? 1000
7 ? 0111
8 & 7 = 0 ? power of 2

5. Clear the least significant 1 bit

n = n & (n - 1);

6. Extract the lowest set bit

int lowest = n & -n;

Example Problem 1: Find the Unique Number

In an array where every number appears twice except one, find the unique number.

Solution Using XOR

All duplicate numbers cancel out:

a ^ a = 0
0 ^ b = b

Implementation

int SingleNumber(int[] nums)
{
    int result = 0;
    foreach (int num in nums)
        result ^= num;
    return result;
}

Time complexity: O(n)
Space: O(1)

Example Problem 2: Subsets Using Bitmasking

Generate all subsets of [1, 2, 3].

Idea

If n = 3, total subsets = 2^3 = 8.
Each bitmask from 0 to 7 represents a subset.

C# Code

void GenerateSubsets(int[] nums)
{
    int n = nums.Length;
    int total = 1 << n;

    for (int mask = 0; mask < total; mask++)
    {
        List<int> subset = new();
        for (int i = 0; i < n; i++)
        {
            if ((mask & (1 << i)) != 0)
                subset.Add(nums[i]);
        }

        Console.WriteLine("[" + string.Join(",", subset) + "]");
    }
}

Example Problem 3: Reverse Bits of a Number

uint ReverseBits(uint n)
{
    uint result = 0;
    for (int i = 0; i < 32; i++)
    {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

Real-Life Applications of Bit Manipulation

1. Cryptography

Bit-level operations secure data.

2. Graphics Processing

Color values and pixel operations use bit shifts.

3. Compression Algorithms

Optimization using binary masks.

4. Competitive Programming

Solving subsets, permutations, and fast checks.

5. Networking

IP addressing, packet flags.

Advantages of Bit Manipulation

• Extremely fast operations

• Reduces memory usage

• Solves problems in fewer steps

• Useful in low-level programming

Disadvantages

• Hard to read and debug

• Not suitable for all problems

Summary

Bit manipulation is a powerful technique that helps solve complex problems quickly by using binary operations.

Key takeaways:

• Works directly on bits (0s and 1s)

• Uses operators like AND, OR, XOR, shifts

• Great for optimization and competitive programming

• Many algorithms can be simplified using bit tricks