SyntaxPilot
Courses/DSA and Coding Problems/Lesson 78
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 78 of 90

Bit manipulation: single number, counting bits, power of two

queued

These are the notes for DSA episode 78. After laundry day every sock in the basket has its twin except one: find the lonely one using only your two hands (constant extra memory). We count every number against every other (correct, then Time Limit Exceeded on 1,000,001 numbers), see why a HashMap is not allowed either, and invent the XOR trick: pairs cancel, one pass, one variable. Then power of two, where Math.log says 2²⁹ is not a power of two, fixed by n & (n - 1); and counting bits, from 32 checks per number to Kernighan's loop to the DP ans[i] = ans[i >> 1] + (i & 1). Three real bugs close it. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

Laundry day In code
The basket of socks the array a
Every sock has a twin every number appears twice
The lonely sock the number that appears once
Only two hands, no table O(1) extra memory
Pick up a sock that matches one in your hand: both go away x ^= v: a pair cancels

Chapati folding (power of two): every fold doubles the layers: 1, 2, 4, 8, 16. Six layers is impossible by folding alone.

Every word, from zero

  • Bit: a single 0 or 1. An int in Java has 32 bits; bit b is worth 2^b. 4 = 100, 1 = 001, 2 = 010.
  • Binary: writing a number in base 2, with bits.
  • Set bit: a bit that is 1. Lowest set bit: the rightmost 1 (12 = 1100: the bit worth 4).
  • ^ (XOR, exclusive or): bit by bit, 1 if the two bits differ. 0^0 = 0, 0^1 = 1, 1^0 = 1, 1^1 = 0.
  • & (AND): 1 only if both bits are 1. x & 1 is the last bit (1 if odd).
  • | (OR): 1 if either bit is 1. It turns bits on and never turns them off.
  • >> (shift right): slide the bits right; i >> 1 drops the last bit (22 → 11). For non-negative i it is i / 2.
  • << (shift left): slide the bits left; 1 << b has only bit b set.
  • Two's complement: how Java stores negative ints; -1 is all 32 bits set, Integer.MIN_VALUE is only the top bit.
  • Constant extra memory, O(1): a fixed number of variables, no matter how big the input.
  • Power of two: 1, 2, 4, 8, ... = 2^p; in binary exactly one set bit.
  • Kernighan's method: count set bits with x &= x - 1 until x == 0; one loop per set bit.
  • Hamming weight / popcount: the number of set bits. Hamming distance: the number of bits where two numbers differ (bitCount(x ^ y)).
  • Floating point (double): an approximate number; Math.log results are rounded.
  • Operator precedence: which operator binds first. In Java + and - bind tighter than ==, which binds tighter than &, ^, |.

Problem statements

1. Single Number (LeetCode 136). Every element of a appears twice except one. Return it in O(n) time and O(1) extra memory.

2. Power of Two (LeetCode 231). Return true if n == 2^p for some p ≥ 0.

3. Counting Bits (LeetCode 338). Return ans[0..n] where ans[i] is the number of 1 bits in i.

Input Answer
{2, 2, 1} 1
{4, 1, 2, 1, 2} 4
{7} (edge: one number) 7
{-3, 5, -3} (edge: negatives) 5
isPow2(536870912) true (2²⁹)
isPow2(0), isPow2(-8) false
countBits(5) [0, 1, 1, 2, 1, 2]

Single number, the obvious way: count every number

import java.util.*;

public class Main {
    static int single(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++)
                if (a[j] == a[i]) count++;
            if (count == 1) return a[i];
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(single(new int[]{2, 2, 1}));
        System.out.println(single(new int[]{4, 1, 2, 1, 2}));
        System.out.println(single(new int[]{7}));
        System.out.println(single(new int[]{-3, 5, -3}));
    }
}
1
4
7
5

Correct on the examples and edge cases. Now 500,000 pairs and one lonely number at the end:

import java.util.*;

public class Main {
    static int single(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++)
                if (a[j] == a[i]) count++;
            if (count == 1) return a[i];
        }
        return -1;
    }
    public static void main(String[] args) {
        int k = 500000, n = 2 * k + 1;
        int[] big = new int[n];
        for (int i = 0; i < k; i++) big[2 * i] = big[2 * i + 1] = i + 1;
        big[n - 1] = 999999;
        long t0 = System.nanoTime();
        int x = single(big);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(n + " numbers: " + x + ", " + ms + " ms");
    }
}
Time Limit Exceeded

Why is it slow?

Every one of the n numbers scans all n numbers: about 10⁶ × 10⁶ = 10¹² comparisons. A HashMap<Integer, Integer> of counts is O(n) time, but it stores up to 500,000 entries: O(n) extra memory, which the problem forbids. We want a running total where a pair cancels itself.

The key insight: XOR cancels pairs

Rule Why
a ^ a = 0 every bit matches itself
a ^ 0 = a XOR with 0 changes nothing
a ^ b = b ^ a, (a ^ b) ^ c = a ^ (b ^ c) order and grouping don't matter

So x = a[0] ^ a[1] ^ ... ^ a[n-1]: the twins cancel wherever they are, and only the lonely number is left.

By hand: 4, 1, 2, 1, 2

Step x in binary x
start, ^ 4 100 4
^ 1 101 5
^ 2 111 7
^ 1 (the 1s cancel) 110 6
^ 2 (the 2s cancel) 100 4

Single number in Java

import java.util.*;

public class Main {
    static int single(int[] a) {
        int x = 0;
        for (int v : a) x ^= v;
        return x;
    }
    public static void main(String[] args) {
        System.out.println(single(new int[]{2, 2, 1}));
        System.out.println(single(new int[]{4, 1, 2, 1, 2}));
        System.out.println(single(new int[]{7}));
        System.out.println(single(new int[]{-3, 5, -3}));
    }
}
1
4
7
5

The million-and-one numbers that timed out:

1000001 numbers: 999999, 7 ms

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// Single number: XOR cancels every pair.
int singleNumber(const vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}
// Power of two: exactly one set bit.
bool isPow2(int n) { return n > 0 && (n & (n - 1)) == 0; }
// Kernighan: one loop per set bit.
int ones(unsigned x) { int c = 0; while (x) { x &= x - 1; c++; } return c; }
// Counting bits: reuse the answer for i >> 1.
vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
    return ans;
}
int main() {
    cout << singleNumber({2, 2, 1}) << " " << singleNumber({4, 1, 2, 1, 2}) << " "
         << singleNumber({7}) << " " << singleNumber({-3, 5, -3}) << "\n";
    for (int n : {1, 16, 6, 1024, 536870912, 0, -8}) cout << n << " " << boolalpha << isPow2(n) << "\n";
    cout << ones(12) << " " << ones(7) << " " << ones(1024) << " " << ones((unsigned)-1) << " " << __builtin_popcount(12) << "\n";
    for (int v : countBits(5)) cout << v << " ";
    cout << "\n";
}
1 4 7 5
1 true
16 true
6 false
1024 true
536870912 true
0 false
-8 false
2 3 1 32 2
0 1 1 2 1 2 

The same solutions in Python

from functools import reduce
from operator import xor

def single_number(a):
    """Every number twice except one: XOR cancels the pairs."""
    x = 0
    for v in a:
        x ^= v
    return x

def is_pow2(n):
    """A power of two has exactly one set bit."""
    return n > 0 and (n & (n - 1)) == 0

def ones(x):
    """Kernighan: x & (x - 1) clears the lowest set bit (x >= 0)."""
    c = 0
    while x:
        x &= x - 1
        c += 1
    return c

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

print(single_number([2, 2, 1]), single_number([4, 1, 2, 1, 2]), single_number([7]), single_number([-3, 5, -3]))
print(reduce(xor, [4, 1, 2, 1, 2]))
for n in [1, 16, 6, 1024, 536870912, 0, -8]:
    print(n, is_pow2(n))
print(ones(12), ones(7), ones(1024), bin(12).count("1"))
print(count_bits(5))
1 4 7 5
4
1 True
16 True
6 False
1024 True
536870912 True
0 False
-8 False
2 3 1 2
[0, 1, 1, 2, 1, 2]

Python ints have no fixed width, so the Kernighan loop in Python is only for x ≥ 0 (for a negative number it would never reach 0); use bin(x).count("1") or x.bit_count() (Python 3.10+) instead.

Power of two

The obvious way: logarithms

import java.util.*;

public class Main {
    static boolean isPow2(int n) {
        if (n <= 0) return false;
        double p = Math.log(n) / Math.log(2);
        return p == Math.floor(p);
    }
    public static void main(String[] args) {
        for (int n : new int[]{1, 16, 6, 1024, 536870912})
            System.out.println(n + " " + isPow2(n));
        System.out.println(Math.log(536870912) / Math.log(2));
    }
}
1 true
16 true
6 false
1024 true
536870912 false
29.000000000000004

536870912 = 2²⁹, and it says false. Math.log works with rounded double values, so log(2²⁹) / log(2) comes out as 29.000000000000004, not 29. Never use floating point for an exact question about integers.

The insight: n & (n − 1) clears the lowest set bit

Binary Value
n 1100 12
n - 1 1011 11 (the lowest 1 becomes 0, the zeros below become 1)
n & (n - 1) 1000 8 (only the lowest set bit is gone)
16 10000 one set bit
16 & 15 00000 0: nothing left, so 16 is a power of two

Subtracting 1 works like an odometer rolling back from 1200 to 1199: the last non-zero digit goes down, every zero after it becomes the largest digit (in binary, 1).

import java.util.*;

public class Main {
    static boolean isPow2(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
    public static void main(String[] args) {
        for (int n : new int[]{1, 16, 6, 1024, 536870912, 0, -8})
            System.out.println(n + " " + isPow2(n));
    }
}
1 true
16 true
6 false
1024 true
536870912 true
0 false
-8 false

Counting bits

The obvious way: 32 checks per number

import java.util.*;

public class Main {
    static int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++)
            for (int b = 0; b < 32; b++)
                if (((i >> b) & 1) == 1) ans[i]++;
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(2)));
        System.out.println(Arrays.toString(countBits(5)));
        System.out.println(Arrays.toString(countBits(0)));
    }
}
[0, 1, 1]
[0, 1, 1, 2, 1, 2]
[0]

Kernighan's method: one loop per set bit

import java.util.*;

public class Main {
    static int ones(int x) {
        int c = 0;
        while (x != 0) {
            x &= x - 1;
            c++;
        }
        return c;
    }
    public static void main(String[] args) {
        System.out.println(ones(12));
        System.out.println(ones(7));
        System.out.println(ones(1024));
        System.out.println(ones(-1));
    }
}
2
3
1
32

-1 is all 32 bits set in two's complement, so it needs 32 loops; 1024 needs only 1.

The DP: reuse the smaller answer

i >> 1 is i without its last bit, a smaller number whose count is already in the table; the dropped bit is i & 1.

i binary i >> 1 i & 1 ans[i]
1 1 0 1 0 + 1 = 1
2 10 1 0 1 + 0 = 1
3 11 1 1 1 + 1 = 2
4 100 2 0 1 + 0 = 1
5 101 2 1 1 + 1 = 2
22 10110 11 0 ans[11] = 3
import java.util.*;

public class Main {
    static int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++)
            ans[i] = ans[i >> 1] + (i & 1);
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(2)));
        System.out.println(Arrays.toString(countBits(5)));
        System.out.println(Arrays.toString(countBits(0)));
    }
}
[0, 1, 1]
[0, 1, 1, 2, 1, 2]
[0]

A race on 50 million numbers:

import java.util.*;

public class Main {
    static int[] slow(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++)
            for (int b = 0; b < 32; b++)
                if (((i >> b) & 1) == 1) ans[i]++;
        return ans;
    }
    static int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++)
            ans[i] = ans[i >> 1] + (i & 1);
        return ans;
    }
    public static void main(String[] args) {
        int n = 50000000;
        long t0 = System.nanoTime();
        int[] a = slow(n);
        long t1 = System.nanoTime();
        int[] b = countBits(n);
        long t2 = System.nanoTime();
        System.out.println("32 checks: " + (t1 - t0) / 1000000 + " ms");
        System.out.println("dp:        " + (t2 - t1) / 1000000 + " ms");
        System.out.println("same? " + Arrays.equals(a, b));
    }
}
32 checks: 3348 ms
dp:        177 ms
same? true

Three real bugs

Bug 1: |= instead of ^=. OR never turns a bit off, so pairs can't cancel.

import java.util.*;

public class Main {
    static int single(int[] a) {
        int x = 0;
        for (int v : a) x |= v;
        return x;
    }
    public static void main(String[] args) {
        System.out.println(single(new int[]{2, 2, 1}));
        System.out.println(single(new int[]{4, 1, 2, 1, 2}));
    }
}
3
7

Bug 2: forgetting n > 0. 0 & -1 = 0, and Integer.MIN_VALUE - 1 overflows to Integer.MAX_VALUE, which shares no bits with it.

import java.util.*;

public class Main {
    static boolean isPow2(int n) {
        return (n & (n - 1)) == 0;
    }
    public static void main(String[] args) {
        System.out.println(isPow2(16));
        System.out.println(isPow2(0));
        System.out.println(isPow2(Integer.MIN_VALUE));
    }
}
true
true
true

Bug 3: no brackets around i & 1. + binds tighter than &, so Java computes (ans[i >> 1] + i) & 1. No error, just wrong counts.

import java.util.*;

public class Main {
    static int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++)
            ans[i] = ans[i >> 1] + i & 1;
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5)));
    }
}
[0, 1, 1, 0, 1, 0]

Complexity

Problem Obvious way Time / space Bit trick Time / space
Single number count each number O(n²) / O(1): Time Limit Exceeded XOR everything O(n) / O(1)
Single number HashMap of counts O(n) / O(n)
Power of two Math.log O(1), wrong for 2²⁹ n > 0 && (n & (n - 1)) == 0 O(1) / O(1)
Counting bits 32 checks per number O(32·n) ans[i >> 1] + (i & 1) O(n) / O(n) for the output
One number's bits 32 checks O(32) Kernighan O(number of set bits)

Common mistakes

Mistake What you see (real) Why Fix
Count each number Time Limit Exceeded n × n comparisons XOR everything once
x \|= v 3 and 7 instead of 1 and 4 OR never clears a bit x ^= v
Math.log(n) / Math.log(2) 536870912 false 29.000000000000004 n > 0 && (n & (n - 1)) == 0
No n > 0 isPow2(0) and isPow2(Integer.MIN_VALUE) are true 0 has no set bits; MIN_VALUE − 1 overflows check n > 0 first
ans[i >> 1] + i & 1 [0, 1, 1, 0, 1, 0] + binds tighter than & ans[i >> 1] + (i & 1)
n & n - 1 == 0 error: bad operand types for binary operator '&' == binds tighter than & (n & (n - 1)) == 0
>> on a negative number in a loop while (x != 0) x >>= 1 never ends (-1 >> 1 == -1) >> copies the sign bit use >>> or Kernighan

Mini project: two lonely socks

Now two socks have lost their twins (LeetCode 260). XOR everything: you get p ^ q, not zero because p != q. Its lowest set bit x & -x is a bit where p and q differ. Split all numbers by that bit and XOR each group: each group holds one lonely sock and complete pairs.

import java.util.*;

public class Sock {
    // Mini project: two lonely socks. Every number twice except TWO (LeetCode 260).
    static int[] twoSingles(int[] a) {
        int x = 0;
        for (int v : a) x ^= v;          // x = p ^ q, not zero because p != q
        int low = x & -x;                // the lowest bit where p and q differ
        int p = 0;
        for (int v : a) if ((v & low) != 0) p ^= v;   // split into two groups
        return new int[]{p, x ^ p};
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSingles(new int[]{1, 2, 1, 3, 2, 5})));
        System.out.println(Arrays.toString(twoSingles(new int[]{-1, 0})));
    }
}
[3, 5]
[-1, 0]

Practice

1. Missing Number (LeetCode 268). 0..n with one number missing. XOR every index and every value.

2. Number of 1 Bits (LeetCode 191). Kernighan.

3. Power of Four (LeetCode 342). A power of two whose one set bit is at an even position: n & 0x55555555.

4. Single Number II (LeetCode 137). Every number three times except one: count each bit mod 3.

5. Hamming Distance (LeetCode 461). The differing bits are the 1s of x ^ y.

Solutions
public class Main {
    // Missing Number (LeetCode 268): XOR every index 0..n and every value; the pairs cancel.
    static int missingNumber(int[] a) {
        int x = a.length;
        for (int i = 0; i < a.length; i++) x ^= i ^ a[i];
        return x;
    }
    // Number of 1 Bits (LeetCode 191): Kernighan.
    static int hammingWeight(int n) {
        int c = 0;
        while (n != 0) { n &= n - 1; c++; }
        return c;
    }
    // Power of Four (LeetCode 342): one set bit, at an even position.
    static boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }
    // Single Number II (LeetCode 137): every number three times except one. Count each bit mod 3.
    static int singleNumberII(int[] a) {
        int ans = 0;
        for (int b = 0; b < 32; b++) {
            int sum = 0;
            for (int v : a) sum += (v >> b) & 1;
            if (sum % 3 != 0) ans |= 1 << b;
        }
        return ans;
    }
    // Hamming distance (LeetCode 461): the differing bits are the 1s of x ^ y.
    static int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
    public static void main(String[] args) {
        System.out.println(missingNumber(new int[]{3, 0, 1}));
        System.out.println(missingNumber(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}));
        System.out.println(hammingWeight(11) + " " + hammingWeight(-3));
        System.out.println(isPowerOfFour(16) + " " + isPowerOfFour(8) + " " + isPowerOfFour(1));
        System.out.println(singleNumberII(new int[]{2, 2, 3, 2}) + " " + singleNumberII(new int[]{0, 1, 0, 1, 0, 1, -99}));
        System.out.println(hammingDistance(1, 4));
    }
}
2
8
3 31
true false true
3 -99
2

Quick quiz

int x = 6 ^ 3 ^ 6;
System.out.println(x);

A) 0 B) 3 C) 5 D) 6

Answer

B) 3. Order doesn't matter: 6 ^ 6 = 0, and 0 ^ 3 = 3.

Interview questions

  1. Why does XOR find the single number? a ^ a = 0, a ^ 0 = a, and XOR is commutative and associative, so all pairs cancel.
  2. Does it work with negative numbers? Yes: XOR works on the 32 bits, whatever they mean.
  3. What does n & (n - 1) do? Clears the lowest set bit.
  4. Why is n > 0 needed in the power-of-two check? 0 has no set bits and Integer.MIN_VALUE has one, but neither is a power of two.
  5. Why not Math.log? Doubles are rounded: log(2²⁹)/log(2) = 29.000000000000004.
  6. What is x & -x? The lowest set bit on its own (two's complement: -x = ~x + 1).
  7. How do you count bits for 0..n in O(n)? ans[i] = ans[i >> 1] + (i & 1) (or ans[i & (i - 1)] + 1).
  8. >> vs >>>? >> copies the sign bit (arithmetic shift); >>> fills with 0 (logical shift).

Glossary

Term Meaning
Bit A single 0 or 1; bit b is worth 2^b
Set bit A bit equal to 1
Lowest set bit The rightmost 1; x & -x
XOR (^) 1 where the bits differ; a ^ a = 0
AND (&) 1 where both bits are 1
OR (\|) 1 where either bit is 1
>> / << Shift bits right / left
>>> Shift right, filling with zeros
Two's complement Java's way of storing negative ints; -1 = all bits set
Power of two 2^p; exactly one set bit
n & (n - 1) n with its lowest set bit cleared
Kernighan's method Count set bits by clearing the lowest one until 0
Popcount / Hamming weight Number of set bits (Integer.bitCount)
Hamming distance Number of differing bits: bitCount(x ^ y)
O(1) extra memory A fixed number of variables
Operator precedence Which operator binds first; + before == before &

Summary

  • Single number: XOR everything; pairs cancel. O(n) time, O(1) memory.
  • Power of two: n > 0 && (n & (n - 1)) == 0, never Math.log.
  • n & (n - 1) clears the lowest set bit: power checks and Kernighan's bit count.
  • Counting bits: ans[i] = ans[i >> 1] + (i & 1), one step per number.
  • Bit operators bind loosely: always bracket them.
  • Next episode: math for coding: GCD, the sieve of Eratosthenes, fast power and modular arithmetic.