DSA — Bit Manipulation

Bitwise Operators

Operator	Name	Example
&	AND	5 & 3 = 1
|	OR	5 | 3 = 7
^	XOR	5 ^ 3 = 6
~	NOT	~5 = -6
<<	Left shift	5 << 1 = 10
>>	Right shift	5 >> 1 = 2

Common Operations

# Check if power of 2
def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

# Get ith bit
def get_bit(num, i):
    return (num >> i) & 1

# Set ith bit
def set_bit(num, i):
    return num | (1 << i)

# Clear ith bit
def clear_bit(num, i):
    return num & ~(1 << i)

# Count set bits
def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

XOR Tricks

# Find unique element (all others appear twice)
def find_unique(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

# Swap without temp
a, b = a ^ b, a ^ b, a ^ b

Mini Practice

1. Check power of 2
2. Count set bits
3. Find unique element
4. Swap without temp variable

Up Next

Continue with Trie — prefix tree data structure.