Bit Manipulation — DSA Mastery

Bitwise Operators

A = B =

Change A and B to see binary operations in real time.

Core Bit Patterns

Pattern	Trick	Use Case
Check ith bit	`(n >> i) & 1`	Is the i-th flag set?
Set ith bit	`n \| (1 << i)`	Turn on the i-th flag
Clear ith bit	`n & ~(1 << i)`	Turn off the i-th flag
Toggle ith bit	`n ^ (1 << i)`	Flip the i-th flag
Remove rightmost 1	`n & (n - 1)`	Count bits, check power of 2
Extract rightmost 1	`n & -n`	Fenwick Trees, isolating bits

XOR Properties

n ^ n = 0

Every number XORed with itself cancels out. Great for finding the "single number" in pairs.

n ^ 0 = n

XORing with 0 leaves the number unchanged.

Commutative & Associative

Order doesn't matter: A ^ B ^ C = C ^ A ^ B.

Counting Bits (Brian Kernighan's Algorithm)

# Counts the number of 1s in binary representation in O(1s) time
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # drops the lowest set bit
        count += 1
    return count

Single Number (XOR Trick)

# All elements appear twice except one. Find it in O(N) time, O(1) space.
def singleNumber(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

Power of Two

# True if n is a power of 2 (has exactly one 1-bit)
def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

LeetCode Problems

EasySingle NumberXOR all elements
EasyNumber of 1 Bitsn & (n - 1)
EasyCounting BitsDP + Bitwise
MediumSingle Number IIState machine / count bits mod 3
MediumSingle Number IIIXOR + isolate bit (n & -n)
MediumBitwise AND of Numbers RangeShift until equal