Bit Manipulation

Theory

Basics of Bits

• Bit: The smallest unit of data in a computer, either 0 or 1.
• Binary Representation: Any integer can be represented in base-2. Example: 5 in binary → 101, 10 in binary → 1010.
• Why Bit Manipulation?
  • Faster than arithmetic operations (O(1) for most operations).
  • Saves space (storing multiple states in a single integer).
  • Useful in problems involving sets, flags, XOR, AND masks.

Common Bitwise Operators

Operator	Symbol	Operation	Example
AND	&	1 & 1 = 1, else 0	5 & 3 = 101 & 011 = 001 = 1
OR	\	0 \ 0 = 0, else 1	5 \ 3 = 101 \ 011 = 111 = 7
XOR	^	1 ^ 1 = 0, 0 ^ 1 = 1	5 ^ 3 = 101 ^ 011 = 110 = 6
NOT	~	Inverts bits	~5 = ~101 = 010 (two’s complement)
Left Shift	<<	Shifts bits left (multiply by 2^n)	5 << 1 = 1010 = 10
Right Shift	>>	Shifts bits right (divide by 2^n)	5 >> 1 = 10 = 2

\ is actually |. The bitwise OR operators which is denote by | can’t be used inside a mdx table

Common Patterns to remember

Common Operations

1. Checking if a bit is set or not

from typing import Final
"""
In binary representation, indexing typically starts from right to left, with the least significant bit (LSB) at
    position 0 and the most significant bit (MSB) at the highest position.

    Intuition:
    - We create a bitmask with only the i-th bit set by left-shifting 1 by i places: (1 << i).
    - Using bitwise AND with the original number keeps only the overlapping set bits.
      If the result is non-zero, the i-th bit in the number was set.
"""
mask: Final[int] = 1 << index
is_set: bool = (number & mask) != 0

Setting the rightmost set bit to 1

if n + 1 == 0:
    return n  # All bits are already set
return n | (n + 1)

Unsetting the rightmost set bit to 1

# Brian Keringhan's Algorithm

if n == 0:
    return 0  # No set bits to unset
return n & (n - 1)

2. Setting Kth bit to 1

"""
Create a mask by left-shifting 1 by k
Apply the mask by OR-ing it with the number
"""

n = 5
k = 1
# 111 → 7
n = n | (1 << k)

3. Setting Kth bit to 0(Clearing Kth bit)

n = 5        # 101
k = 0
n = n & ~(1 << k)  # 100 → 4

4. Toggling Kth bit

n = 5        # 101
k = 0
n = n ^ (1 << k)  # 100 → 4

5. Counting set bits

def count_set_bits(n: int) -> int:
    """
    Count the number of set bits (1s) in the binary representation of a number.

    Intuition:
    - We need to count how many 1s are present in the binary representation of n.
    - We can use bitwise operations to check each bit position.
    - There are several approaches: iterative, Brian Kernighan's algorithm, and built-in functions.
    - The key insight is that we can repeatedly remove the least significant set bit.

    Approach:
    1. Initialize a counter to 0.
    2. While n is greater than 0:
       - Check if the least significant bit is set using n & 1.
       - Add 1 to counter if bit is set.
       - Right shift n by 1 to check the next bit.
    3. Return the final count.

    Key Insights:
    - n & 1 checks if the least significant bit is set.
    - n >>= 1 removes the least significant bit (equivalent to n // 2).
    - We continue until n becomes 0.
    - This approach works for both positive and negative numbers.

    Example:
    n = 13 (binary: 1101)
    Iteration 1: n & 1 = 1, count = 1, n = 6 (110)
    Iteration 2: n & 1 = 0, count = 1, n = 3 (11)
    Iteration 3: n & 1 = 1, count = 2, n = 1 (1)
    Iteration 4: n & 1 = 1, count = 3, n = 0
    Result: 3 set bits

    Time Complexity: O(log n) - proportional to the number of bits
    Space Complexity: O(1) - constant space
    """
    count = 0
    while n > 0:
        count += n & 1  # Add 1 if least significant bit is set
        n >>= 1        # Right shift to check next bit
    return count

"""
Brian Kernighan’s Algorithm
"""
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

6. Power of Two Check

"""
Check if only a single bit is set in a number.
If the number is a power of two, then the number and its complement would have only one bit set.
"""
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

7. XOR Tricks

XOR Properties:

1. a ^ a = 0
2. a ^ 0 = a
3. a ^ b ^ a = b (commutative and associative)

Applications: Find unique number in array where every other number occurs twice.

arr = [2, 3, 2, 4, 4]
res = 0
for num in arr:
    res ^= num
print(res)  # Output: 3

8. Subset generation using bits

# Use an integer to represent subset
arr = [1, 2, 3]
n = len(arr)
for mask in range(1 << n):
    subset = [arr[i] for i in range(n) if mask & (1 << i)]
    print(subset)

9. Swapping Numbers Using XOR

a = 5
b = 3
a ^= b
b ^= a
a ^= b

10. Finding Rightmost Set Bit

n = 10    # 1010
rightmost = n & -n  # 0010 → 2

11. Clearing Rightmost Set Bit

n = 10    # 1010
n = n & (n - 1)  # 1000

Tip for Interviews:

1. Always think in terms of 0 and 1.
2. Many problems on Leetcode: Single Number, Counting Bits, Subset Sum DP, Missing Number, Power of Two.
3. Visualize bits as switches — “on/off” to simplify reasoning.

Algorithms

Brian Kernighan’s Algorithm

Brian Kernighan’s Algorithm is one of the most elegant and widely used bit manipulation tricks in DSA, especially for counting set bits efficiently

Trick: n & (n-1) removes the rightmost set bit from n.

• Every time you do n = n & (n-1), you remove one 1(rightmost)
• Count how many times you can do this → number of 1s

Why does it work?

• n - 1 flips all bits after the rightmost 1, including that 1 itself
• ANDing it with n removes that rightmost 1

    # Step 1: n = 1100
    n-1 = 1011
    n & (n-1) = 1100 & 1011 = 1000  # removes rightmost 1

    # Step 2: n = 1000
    n-1 = 0111
    n & (n-1) = 1000 & 0111 = 0000  # removes last 1

algorithm.py

def count_set_bits(n):
    count = 0
    while n:
        n &= (n-1)  # remove rightmost set bit
        count += 1
    return count

# Example
n = 13
print(count_set_bits(n))  # Output: 3

---

Problem Set

In python, Logical AND is different from Bitwise &

Solution to All recursion solutions Github

Basics

1. Check if the ith bit is set
2. Check if a number is odd or not
3. Check if a number is power of 2 or not
4. Count the number of set bits
5. Set/Unset the rightmost unset bit T
6. Swap two numbers Trick
7. Divide two numbers Trick

Medium Problems

1. Count the number of bits to be flipped to convert A to B
2. Single Number
3. Power set
4. Find xor of numbers from L to R
5. Find the two numbers appearing odd number of times

Math problems

1. Print Prime Factors of a Number
2. All Divisors of a Number
3. Sieve of Eratosthenes
4. Find Prime Factorisation of a Number using Sieve
5. Power(n, x)