DSA Bit Manipulation

Bit manipulation means working directly with the 0s and 1s that make up numbers inside a computer. Operations on bits run extremely fast, because the processor handles them in a single step. Clever bit tricks replace loops and extra memory in many problems.

Picture a row of light switches on a wall. Each switch is either off (0) or on (1). The whole row together encodes a number. Flipping one switch changes the number in a predictable way. Bit manipulation means flipping, checking, and combining those switches on purpose.

Binary Numbers

Computers store numbers in base 2. Each position holds a power of two.

Number 13 in binary

Position value:  8   4   2   1
Bit:             1   1   0   1

8 + 4 + 0 + 1 = 13

print(bin(13))        # 0b1101
print(int("1101", 2)) # 13

The Bitwise Operators

a = 5   # 101
b = 3   # 011

a & b    # AND  -> 001 = 1   (1 only where both bits are 1)
a | b    # OR   -> 111 = 7   (1 where either bit is 1)
a ^ b    # XOR  -> 110 = 6   (1 where the bits differ)
~a       # NOT  -> flips every bit
a << 1   # left shift  -> 1010 = 10 (multiply by 2)
a >> 1   # right shift -> 010 = 2   (divide by 2, drop remainder)

• AND keeps a bit only when both inputs have it.
• OR keeps a bit when either input has it.
• XOR keeps a bit when the inputs differ. XOR of a number with itself gives 0.
• Shifts slide all bits left or right by a set count.

Useful Tricks

Check Odd or Even

The last bit decides it. A last bit of 1 means odd.

def is_odd(n):
    return (n & 1) == 1

print(is_odd(7))   # True
print(is_odd(10))  # False

Check a Power of Two

A power of two has exactly one bit set. Subtracting 1 flips that bit and every bit after it, so AND-ing the two gives 0.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(16))   # True
print(is_power_of_two(18))   # False

16 = 10000
15 = 01111
AND = 00000  (power of two)

Count the Set Bits

The expression n & (n - 1) removes the lowest set bit. Counting how many times you can repeat it gives the total.

def count_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

print(count_bits(13))   # 3  (1101 has three 1s)

Get, Set, Clear, and Toggle a Bit

n = 10        # 1010
i = 2

get    = (n >> i) & 1      # 0
set_   = n | (1 << i)      # 1110 = 14
clear  = n & ~(1 << i)     # 1010 = 10
toggle = n ^ (1 << i)      # 1110 = 14

Example: Find the Single Number

Every number in a list appears twice except one. XOR cancels matching pairs, so only the lonely number survives.

def single_number(numbers):
    result = 0
    for n in numbers:
        result ^= n
    return result

print(single_number([4, 1, 2, 1, 2]))   # 4

The solution uses O(1) extra memory. A dictionary approach would need O(n).

Bit Masks

A bit mask is a number whose 1 bits mark the positions you care about. Suppose a settings number stores four options, one per bit. The mask 0b0101 selects options one and three. AND-ing the settings with the mask reveals only those two options. OR-ing turns them on, and AND-ing with the flipped mask turns them off. One integer replaces four separate variables.

Real-Life Uses

Permission systems store many yes-or-no settings inside one number. Graphics code packs red, green, and blue color values into a single integer. Networking tools use bit masks to decide which part of an address identifies a network. Compression and encryption routines rely on fast bit operations.

Common Mistakes

Operator precedence causes trouble. Languages such as C bind == tighter than &, while Python orders them differently. Wrap bit operations in parentheses to keep the meaning clear everywhere. Using the right shift on negative numbers behaves differently across languages. Confusing the logical word "and" with the bitwise symbol & produces wrong results. Print values in binary with bin() while learning to see what happens.

Complexity Summary

• Single bit operations take O(1).
• Counting set bits with the trick takes O(k), where k is the number of 1 bits.
• Most tricks need O(1) extra space.

Key Points

• Numbers consist of bits, and operators act on each bit.
• AND, OR, XOR, NOT, and shifts form the basic toolkit.
• n & (n - 1) removes the lowest set bit.
• XOR cancels equal pairs.
• Bit tricks save time and memory.