Bit Manipulation

Step 1 Understand it

Remember it by

XOR cancels pairs (a ^ a = 0), and x & (x − 1) deletes the lowest 1 bit.

Watch it happen

The idea

Numbers are stored as bits, and bitwise operators work on all bits at once. A few facts solve most problems: x ^ x = 0 and x ^ 0 = x; x & 1 is the last bit; x >> 1 drops the last bit; x & (x − 1) removes the lowest set bit.

Picture it

flowchart LR
  A["4 ^ 1 ^ 2 ^ 1 ^ 2"] -->|"reorder freely"| B["4 ^ (1 ^ 1) ^ (2 ^ 2)"] --> C["4 ^ 0 ^ 0"] --> D["4"]

Analogy

A row of light switches. XOR with a pattern flips those switches; flipping the same pattern twice puts everything back.

Where the analogy breaks

Switches don't overflow. In Java or C, integers have a fixed number of bits and can overflow; Python integers grow, so problems like Sum of Two Integers need a mask in Python.

Step 2 Recognise it

Words that signal it

• 'Every element appears twice except one'
• 'Count the 1 bits', 'reverse the bits'
• 'Without using + or −'
• 'Missing number' in 0…n (XOR or the sum formula)

Don't confuse it with

• Arrays & Hashing: A hash set also finds the single number, but with O(n) memory; XOR does it with O(1).
• Math: Missing Number can also use n(n + 1)/2 − sum; XOR avoids any overflow worry.

Gut check

Pairs cancelling, single bits, or 'no + allowed'? → bits.

How to recognise it in an interview

The prompt explicitly mentions '32-bit integers', 'Constant space O(1)', or 'Find the missing/single number'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def bit_tricks(x):
    last_bit = x & 1               # 1 if x is odd
    x_without_last = x >> 1        # drop the last bit (x // 2)
    lowest_removed = x & (x - 1)   # remove the lowest 1 bit
    count = 0
    while x:
        x &= x - 1                 # one loop per 1 bit
        count += 1
    return last_bit, x_without_last, lowest_removed, count

def single(nums):
    acc = 0
    for x in nums:
        acc ^= x                   # pairs cancel: a ^ a = 0
    return acc

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num; // XOR magically cancels out any duplicates!
        }
        return result;
    }
}

Common mistakes

• Python's ~ and right shifts on negative numbers behave differently from Java's.
• Forgetting operator precedence: write (x & 1) == 1, with brackets.
• In Python, not masking with 0xFFFFFFFF when simulating 32-bit integers.
• Confusing && (Logical AND for booleans) with & (Bitwise AND for bits) in your if-statements.
• Assuming bitwise operations are readable! They look like gibberish if you don't add comments.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def single_number(nums):
    acc = 0
    for x in nums:
        acc ^= x
    return acc

def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Single Number" as solved Single Number Easy

   Every number appears twice except one; find it with O(1) extra space.

   Show answer

   Technique: XOR

   The clue: Pairs + one leftover + constant space.

   The trick: XOR everything; pairs cancel to 0.

2. Mark "Number of 1 Bits" as solved Number of 1 Bits Easy

   Count the 1 bits in an integer.

   Show answer

   Technique: Bit counting with n & (n − 1)

   The clue: 'Count the bits'.

   The trick: n & (n − 1) removes the lowest 1 bit; count how many times until n is 0.

3. Mark "Counting Bits" as solved Counting Bits Easy

   For every i from 0 to n, count the 1 bits in i.

   Show answer

   Technique: DP on bits

   The clue: Bit counts for every number up to n, in O(n).

   The trick: bits[i] = bits[i >> 1] + (i & 1).

4. Mark "Reverse Bits" as solved Reverse Bits Easy

   Reverse the 32 bits of an unsigned integer.

   Show answer

   Technique: Bit-by-bit shifting

   The clue: Work on the binary form directly.

   The trick: 32 times: take n's last bit, shift the result left and add it, shift n right.

5. Mark "Missing Number" as solved Missing Number Easy

   Numbers 0 … n with one missing; find it.

   Show answer

   Technique: XOR (or the sum formula)

   The clue: One missing value from a known complete range.

   The trick: XOR all indexes 0 … n and all values; everything present cancels out, leaving the missing one.

Medium

1. Mark "Sum of Two Integers" as solved Sum of Two Integers Medium

   Add two integers without using + or −.

   Show answer

   Technique: XOR for the sum, AND + shift for the carry

   The clue: 'Without + or −'.

   The trick: a ^ b adds without carrying; (a & b) << 1 is the carry; repeat until there's no carry (mask to 32 bits in Python).

2. Mark "Reverse Integer" as solved Reverse Integer Medium

   Reverse the digits of a 32-bit signed integer, returning 0 if it overflows.

   Show answer

   Technique: Digit popping with an overflow check

   The clue: Digits + a 32-bit limit.

   The trick: Pop the last digit with % 10 and push it onto the result × 10; check the limit before each push.

What to say in the interview

'Since we have a rigid space limitation and are dealing with pairing logic, I can use the XOR operator to cancel out duplicate binary flags.'

Follow-up prep

How do you check if a number is a power of 2 using only bitwise? (Hint: (n & (n - 1)) == 0).