☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Number of 1 Bits

Easy TUF ID 2402 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a 32-bit integer n, return how many 1 bits its binary representation has. This count is also called the Hamming weight or popcount.

The original LeetCode version passes an unsigned 32-bit integer. Java has no unsigned int, so such a value arrives as an int with the same bit pattern: 4294967293 (binary 111...1101) arrives as -3. Only the pattern matters for counting bits, so every method below treats n as 32 raw bits, and -1 has 32 set bits. (The current LeetCode statement restricts n to 1 ≤ n ≤ 2^31 - 1; the methods handle that as a special case.)

Example 1

n = 11
answer = 3          // 11 = 1011

Example 2

n = 4294967293 (the int -3)
answer = 31         // 11111111111111111111111111111101

Approach 1: Brute force, test each of the 32 bits

Intuition. The popcount is the sum, over all 32 positions, of the bit at that position. (n >>> i) & 1 moves bit i to the bottom and isolates it. Test every position and count the ones.

Algorithm.

  1. count = 0.
  2. For i from 0 to 31: if (n >>> i) & 1 is 1, increment count.
  3. Return count.
static int bruteForce(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) == 1) count++;
    }
    return count;
}

Complexity. Time O(32): always 32 rounds, even for n = 1. Space O(1).

A popular variant shifts n itself, while (n != 0) { count += n & 1; n >>>= 1; }, which stops after the highest set bit. It must use the unsigned shift >>>. With the arithmetic shift >>, a negative n keeps copying its sign bit into the top, never reaches 0, and the loop runs forever.

Approach 2: Optimal, Brian Kernighan’s trick

Intuition. Instead of visiting every position, jump straight from one 1 to the next. Subtracting 1 from n turns its lowest 1 into 0 and every 0 below it into 1, leaving the higher bits alone:

n         = 1011 0100
n - 1     = 1011 0011
n & (n-1) = 1011 0000      // exactly the lowest 1 has been cleared

The AND keeps the higher bits (unchanged in both) and wipes the changed tail (the two patterns disagree on every bit of it). So n &= n - 1 deletes exactly one 1 per round, and the number of rounds until n is 0 is the answer.

Algorithm.

  1. count = 0.
  2. While n != 0: set n = n & (n - 1) and increment count.
  3. Return count.
static int optimal(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;     // drop the lowest 1
        count++;
    }
    return count;
}

Dry run on n = 11:

round n before n - 1 n & (n - 1) count
1 1011 1010 1010 1
2 1010 1001 1000 2
3 1000 0111 0000 3

Negative values are fine too. For Integer.MIN_VALUE (only the top bit set), n - 1 wraps around to Integer.MAX_VALUE, the AND is 0, and the loop stops after one round with the correct count 1.

Complexity. Time O(k) where k is the number of set bits, at most 32. Space O(1). This is the version to write in an interview: short, obviously terminating, and faster than Approach 1 on sparse inputs.

Approach 3: Counting in parallel (SWAR)

Intuition. The loops above handle one bit, or one set bit, per round. We can instead treat the 32-bit word as a row of small counters and add neighbouring counters together, all in the same instruction. This is “SIMD within a register” (SWAR), and it is how Integer.bitCount is implemented in the JDK.

  1. Pairs. For a 2-bit field with high bit h and low bit l, its value is 2h + l and its popcount is h + l. Subtracting h converts one into the other, and (n >>> 1) & 0x55555555 lines up each h under its own field. The result is never negative, so no borrow crosses into the neighbouring field. Each 2-bit field now holds a count from 0 to 2.
  2. Nibbles. 0x33333333 keeps the lower 2-bit count of each nibble; shifting by 2 and masking again brings the upper count down; adding gives each nibble a count from 0 to 4.
  3. Bytes. Add each nibble to its neighbour with n + (n >>> 4) and mask with 0x0f0f0f0f. A byte’s count is at most 8, which fits in 4 bits, so nothing overflows into the next field before the mask removes the garbage.
  4. Halves and whole word. Two more shift-and-add steps sum the bytes. Each lower byte now holds a partial sum, and the lowest byte holds the total, at most 32. The final & 0x3f keeps just those 6 bits.

A one-byte illustration with 1011 0110 (five ones): pairs 10|11|01|10 become counts 01|10|01|01, nibbles become 0011|0010 (3 and 2), and the byte becomes 0000 0101, which is 5.

static int parallel(int n) {
    n = n - ((n >>> 1) & 0x55555555);                  // every 2-bit field holds its own count (0..2)
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);   // every 4-bit field holds its count (0..4)
    n = (n + (n >>> 4)) & 0x0f0f0f0f;                  // every byte holds its count (0..8)
    n = n + (n >>> 8);                                 // low byte of each 16-bit half: count of that half
    n = n + (n >>> 16);                                // low byte of the word: count of all 32 bits
    return n & 0x3f;                                   // the answer is at most 32, which fits in 6 bits
}

Complexity. Time O(1): about a dozen operations with no loop and no branch, regardless of the input. Space O(1). In production code just call Integer.bitCount(n); the JIT usually compiles it to the CPU’s single popcount instruction.

Edge cases and pitfalls