DSA — Techniques

Bit Manipulation

Operate directly on binary representations. Extremely fast — single CPU instruction. Useful for flags, sets, and optimization.

— min read

O(1)Most Ops

ANDOR XOR NOT

Shifts<< >>

SetClear Toggle

✓Space Opt.

// BITWISE OPERATIONS VISUALIZER

Enter two numbers and choose a bitwise operation

Operations

Python Code

Tricks

Quiz

Practice

AND (&)

Both bits must be 1. Used to check/clear bits.

n & 1 — check if odd; n & (n-1) — clear lowest set bit

OR (|)

At least one bit is 1. Used to set bits.

n | (1 << k) — set bit k

XOR (^)

Bits differ. Self-inverse: a^a=0, a^0=a.

a ^ b ^ b == a — find unique element

Shift (<<, >>)

Left shift = ×2. Right shift = ÷2.

n << 1 = n*2; n >> 1 = n//2

python

# Common bit tricks
n = 12  # 1100 in binary

n & 1          # check if odd → 0 (even)
n & (n-1)    # clear lowest set bit → 8
n | (n-1)    # set all bits below MSB
n ^ n         # XOR with self → 0
n >> 1        # divide by 2 → 6
n << 1        # multiply by 2 → 24

# Count set bits (Brian Kernighan)
def count_bits(n):
    count = 0
    while n:
        n &= n - 1  # clears lowest set bit
        count += 1
    return count

n&(n-1)

Clear Low Bit

Turn off rightmost 1 — check power of 2

n^n = 0

XOR Self

Find single non-duplicate in array

n>>1

Divide by 2

Right shift = floor division by 2

n<<k

Multiply 2^k

Fastest multiply by power of 2

XOR of a number with itself equals:

Progress 0 / 7 solved

7 problems · 4 PBC · 3 Startup

#112 Single Number Amazon, Google PBC →

#113 Power of Two Microsoft, Google PBC →

#114 Sum of Two Integers Meta, Amazon PBC →

#115 Steps to Reduce Number to Zero Apple PBC →

#116 Check if a Number is Sparse Cogoport STARTUP →

#117 Swap All Odd and Even Bits PhonePe STARTUP →

#118 Check if Power of 4 Apna STARTUP →

← Sliding Window