Bit Manipulation Tutorial: Master XOR Tricks & Bitwise Operations for Interviews

Complete guide to bit manipulation with essential tricks for coding interviews. Learn XOR patterns, power of 2 checks, bit masks, and bitwise operators in Python. Solve single number and subset problems in O(1) space

📅 Published: July 22, 2025 ✏️ Updated: August 18, 2025 By Ojaswi Athghara
#bits #xor-tricks #bitwise #power-of-two #bit-masking #leetcode

Bit Manipulation Tutorial: Master XOR Tricks & Bitwise Operations for Interviews

The XOR Trick That Blew My Mind

I'll never forget the first time I saw an elegant bit manipulation solution. The interviewer asked: "Find the number that appears once in an array where every other number appears twice."

My first instinct: use a hash map. Track counts, return the one with count = 1. The interviewer smiled and said, "Can you do it in O(1) space?"

I was stuck. Then they showed me: result = 0; for num in array: result ^= num. Three lines. O(1) space. I was amazed.

That's when I learned: bit manipulation isn't about being clever—it's about knowing a handful of tricks that solve specific problem patterns. Once you know these tricks, you'll write solutions that feel like magic.

In this guide, I'll share the essential bit manipulation patterns that transformed my interviews. No complex theory—just practical tricks you can use immediately.

The Bit Manipulation Toolkit

Basic Operators

& (AND)   # Both bits must be 1
| (OR)    # At least one bit is 1
^ (XOR)   # Bits are different
~ (NOT)   # Flip all bits
<< (Left shift)   # Multiply by 2^n
>> (Right shift)  # Divide by 2^n

Truth tables:

AND  |  OR  | XOR
a b  |  a b | a b
0 0=0|  0 0=0| 0 0=0
0 1=0|  0 1=1| 0 1=1
1 0=0|  1 0=1| 1 0=1
1 1=1|  1 1=1| 1 1=0

Essential Bit Tricks

# Check if ith bit is set
def is_bit_set(num, i):
    return (num & (1 << i)) != 0

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

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

# Toggle ith bit
def toggle_bit(num, i):
    return num ^ (1 << i)

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

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

Pattern 1: XOR Tricks (The Most Important)

XOR has magical properties:

  • a ^ a = 0 (anything XOR itself = 0)
  • a ^ 0 = a (anything XOR 0 = itself)
  • XOR is commutative and associative

Find Single Number

LeetCode #136 - Single Number

def single_number(nums):
    """
    Find number that appears once (others appear twice).
    XOR all numbers: duplicates cancel out!
    """
    result = 0
    for num in nums:
        result ^= num
    return result

Why this works:[4, 1, 2, 1, 2] → 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4

Time: O(n), Space: O(1)

Find Two Single Numbers

LeetCode #260 - Single Number III

Two numbers appear once, others twice. How to separate them?

def single_number_iii(nums):
    """
    Two numbers appear once, find both.
    1. XOR all: result = a ^ b
    2. Find any set bit in result (where a and b differ)
    3. Partition numbers by that bit, XOR each group
    """
    # XOR all numbers: get a ^ b
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Find rightmost set bit (where a and b differ)
    rightmost_bit = xor_all & (-xor_all)

    # Partition and XOR each group
    a, b = 0, 0
    for num in nums:
        if num & rightmost_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]

Genius insight: If a ^ b has a set bit at position i, then a and b differ at that bit. Use this to partition all numbers into two groups!

Missing Number

LeetCode #268 - Missing Number

def missing_number(nums):
    """
    Find missing number from 0 to n.
    XOR all indices with all values: missing number remains!
    """
    result = len(nums)  # Start with n

    for i, num in enumerate(nums):
        result ^= i ^ num  # XOR index and value

    return result

Why: If array was complete, each number would XOR with itself (cancel out). The missing number only appears in indices, so it survives!

Pattern 2: Power of Two Checks

Powers of two have exactly one set bit: 1, 2, 4, 8, 16... = 1, 10, 100, 1000, 10000 in binary.

Check Power of Two

def is_power_of_two(n):
    """
    Check if n is power of 2.
    Trick: n & (n-1) removes rightmost bit.
    Power of 2 has only one bit, so result is 0!
    """
    return n > 0 and (n & (n - 1)) == 0

Examples:

  • 8 = 1000, 7 = 0111, 8 & 7 = 0000 ✓
  • 6 = 0110, 5 = 0101, 6 & 5 = 0100 ✗

Count Powers of Two in Range

def count_powers_of_two(n):
    """
    Count how many powers of 2 are ≤ n.
    """
    if n < 1:
        return 0
    return n.bit_length()  # Or: int(log2(n)) + 1

Pattern 3: Bit Counting and Manipulation

Count Set Bits (Hamming Weight)

LeetCode #191 - Number of 1 Bits

def hamming_weight(n):
    """
    Count number of 1 bits.
    Trick: n & (n-1) removes rightmost 1 bit.
    """
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

Alternative:

def hamming_weight_v2(n):
    """Count set bits using Brian Kernighan's algorithm."""
    return bin(n).count('1')

Reverse Bits

LeetCode #190 - Reverse Bits

def reverse_bits(n):
    """
    Reverse bits of 32-bit integer.
    Extract each bit from right, build result from left.
    """
    result = 0
    for _ in range(32):
        # Shift result left, add rightmost bit of n
        result = (result << 1) | (n & 1)
        n >>= 1  # Move to next bit
    return result

Pattern 4: Subset Generation

Generate all subsets using bit masks!

All Subsets

def all_subsets(nums):
    """
    Generate all subsets using bit masks.
    For n elements, there are 2^n subsets.
    Each number 0 to 2^n-1 represents a subset.
    """
    n = len(nums)
    result = []

    # Iterate through all possible bit masks
    for mask in range(1 << n):  # 2^n possibilities
        subset = []

        # Check each bit
        for i in range(n):
            if mask & (1 << i):  # If ith bit is set
                subset.append(nums[i])

        result.append(subset)

    return result

Example for [1,2,3]:

  • mask=0 (000) → []
  • mask=1 (001) → [1]
  • mask=2 (010) → [2]
  • mask=3 (011) → [1,2]
  • mask=4 (100) → [3]
  • ...
  • mask=7 (111) → [1,2,3]

Pattern 5: Bit Masks for State Representation

Use integers to represent sets or boolean states compactly.

Sum of Two Integers (No + Operator)

LeetCode #371 - Sum of Two Integers

def get_sum(a, b):
    """
    Add two numbers without + operator.
    Use XOR for sum, AND<<1 for carry.
    """
    mask = 0xFFFFFFFF  # 32-bit mask

    while b != 0:
        # XOR gives sum without carry
        # AND<<1 gives carry
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask

    # Handle negative numbers
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Why this works:

  • 3 + 5 = 011 + 101
  • Sum without carry: 011 ^ 101 = 110
  • Carry: (011 & 101) << 1 = 010
  • Repeat: 110 + 010 = ...

Maximum XOR of Two Numbers

LeetCode #421

def find_maximum_xor(nums):
    """
    Find maximum XOR of two numbers.
    Build result bit by bit from left.
    """
    max_xor = 0
    mask = 0

    # Build result bit by bit (31 bits for integers)
    for i in range(31, -1, -1):
        mask |= (1 << i)  # Add current bit to mask
        prefixes = {num & mask for num in nums}

        # Try to set current bit in result
        temp = max_xor | (1 << i)

        # Check if temp is achievable
        for prefix in prefixes:
            if temp ^ prefix in prefixes:
                max_xor = temp
                break

    return max_xor

Bit Manipulation Interview Patterns

Pattern Recognition Guide:

1. "Find number that appears once (others appear twice/thrice)" → XOR tricks

2. "Check if power of 2 / count powers of 2" → n & (n-1) trick

3. "Count set bits / manipulate specific bits" → Bit masking and shifting

4. "Generate all subsets" → Iterate through 0 to 2^n-1 as bit masks

5. "Perform operation without arithmetic operators" → Bit manipulation simulation

Common Bit Manipulation Tricks

Swap Two Numbers

def swap(a, b):
    """Swap without temporary variable."""
    a ^= b
    b ^= a  # b = b ^ (a ^ b) = a
    a ^= b  # a = (a ^ b) ^ a = b
    return a, b

Get Rightmost Set Bit

def rightmost_set_bit(n):
    """Get rightmost 1 bit."""
    return n & -n  # -n is two's complement

Remove Rightmost Set Bit

def remove_rightmost_bit(n):
    """Turn off rightmost 1 bit."""
    return n & (n - 1)

Check if Opposite Signs

def opposite_signs(x, y):
    """Check if two integers have opposite signs."""
    return (x ^ y) < 0

Multiply/Divide by 2^n

def multiply_by_power_of_2(num, n):
    return num << n  # num * 2^n

def divide_by_power_of_2(num, n):
    return num >> n  # num // 2^n

When NOT to Use Bit Manipulation

Avoid bit manipulation when:

  • Makes code significantly less readable
  • Premature optimization (profile first!)
  • Language/compiler already optimizes
  • Not a recognized pattern (confuses others)

Use bit manipulation when:

  • Space optimization is critical
  • Recognized interview pattern (XOR tricks, power of 2)
  • Significant performance gain proven
  • Problem naturally fits bit representation

Common Pitfalls

Mistake 1: Signed vs Unsigned

# Python integers are arbitrary precision
# Be careful with negative numbers

# WRONG for negative numbers
def is_even(n):
    return (n & 1) == 0  # Works, but...

# For Java/C++, be careful with sign bit

Mistake 2: Operator Precedence

# WRONG: & has lower precedence than ==
if n & 1 == 0:  # Parsed as: n & (1 == 0)

# RIGHT: Use parentheses
if (n & 1) == 0:

Mistake 3: Off-by-One in Bit Positions

# Bits are 0-indexed!
# For 32-bit integer: bits 0 to 31
# Not 1 to 32!

My Practice Strategy

Week 1: Master the Basics

  • Understand all operators deeply
  • Practice basic tricks (set, clear, toggle bits)
  • Implement 10-15 helper functions

Week 2: XOR Patterns

  • Single number variations
  • Missing number problems
  • 15-20 XOR problems

Week 3: Advanced Patterns

  • Subset generation with masks
  • State representation
  • Maximum XOR problems

Week 4: Mixed Practice

  • 30-40 problems across all patterns
  • Recognize when bit manipulation helps
  • Practice explaining solutions

Real Interview Success

I was asked: "Find two elements that appear once in an array where all others appear twice."

My approach:

  1. "Two single numbers" → XOR pattern
  2. XOR all → get a ^ b
  3. Find differing bit → partition numbers
  4. XOR each partition → get a and b

Coded in 10 minutes. The interviewer was impressed by the elegant O(1) space solution.

Conclusion: Your Bit Manipulation Mastery

Bit manipulation isn't about memorizing tricks—it's about recognizing patterns:

  1. XOR for finding unique elements - Most common pattern
  2. n & (n-1) for power of 2 - Simple and elegant
  3. Bit masks for subsets - Generate all possibilities
  4. Shifting for multiplication/division by 2 - Basic optimization

Start with XOR problems. They're the most common and most impressive. Then learn power-of-2 checks. Finally, tackle bit masks and counting.

Within 2-3 weeks, you'll recognize bit manipulation opportunities and write solutions that feel like magic to others.

Remember: the best bit manipulation solution is one that's both efficient AND readable. Don't sacrifice clarity for cleverness!

Happy coding, and may your bits always be aligned!

If you found this guide helpful, share it with others learning algorithms. Bit manipulation is a powerful optimization tool when used wisely. If this guide helped you master bit manipulation or understand XOR tricks for interviews, I'd love to hear about it! Connect with me on Twitter or LinkedIn.

Support My Work

If this guide helped you understand bit manipulation, master XOR tricks, or ace bitwise interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.

☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!

Cover image by Kamil Switalski on Unsplash

Related Blogs

Ojaswi Athghara

SDE, 4+ Years

© ojaswiat.com 2025-2027