#71 · Bit Manipulation

Number of 1 Bits

Given an unsigned integer, return the number of 1 bits in its binary representation (its Hamming weight).

EasyLeetCode

Bit being examined
Counted / set / result
Related bit
Cleared / carried

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Bits of an integer

An integer is a row of bits. Shifting moves the bits one place, AND with 1 reads the lowest bit, and AND with a mask keeps only chosen bits. The bit tricks here combine these to count or clear bits without looping over all 32 positions.

Memory layout

A single machine word (32 bits here); every operation below works on registers, not memory.

Operation	Cost
test one bit	O(1)
count all bits	O(32), O(bits set) or O(1) depending on the method

The identity n & (n − 1)

Subtracting 1 flips the lowest 1 bit to 0 and all zeros below it to 1. AND-ing with n therefore clears exactly the lowest set bit. Repeating it counts the set bits one by one.

Memory layout

One register.

Operation	Cost
iterations	number of set bits

Why it fits

The answer depends only on the bit pattern, so bit operations are the natural tools: no arrays, no strings.
Kernighan's trick makes the work proportional to the number of ones instead of the word size, which matters for sparse numbers.
Counting in parallel (adding neighbouring fields) uses the fact that a word is wide enough to hold many small counters at once.

Why alternatives degrade

Converting to a binary string and counting "1":: Allocates a string and is slower; it also hides the bit-level insight the problem tests.
Lookup table of all 32-bit values:: Four billion entries: far too large. A table for 8 or 16 bits works (split the word), but is memory for no real gain over the SWAR method.
Division by 2 with remainder:: It works for non-negative numbers (n % 2, n / 2), but is just a slow way to write shift and mask, and misbehaves for negative signed values.

Four approaches, from naive to production

1 · beginner

Test each of the 32 positions

time O(32) = O(1)space O(1)

For every position i from 0 to 31, shift n right by i, mask the lowest bit and add it to the count.

int hammingWeight(uint32_t n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n >> i) & 1) count++;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) != 0) count++;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    for i in range(32):
        if (n >> i) & 1: count += 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) count++;
  }
  return count;
}

Flaws & bottlenecks

Always 32 iterations, even for numbers with only a few bits or a small value.
Needs the unsigned right shift (>>>) in languages with signed integers, or the sign bit gives wrong results.
Does not use any property of the number.

Interviewer cross-questions

Why use >>> and not >> in JavaScript or Java?

Say: >> keeps the sign bit (arithmetic shift), so a negative number would keep shifting in ones and the loop logic would count wrongly. >>> shifts in zeros.

How many iterations does it always take?

Say: Exactly the word size, 32, regardless of how many bits are set.

How can you stop earlier?

Say: Shift n itself and stop when it becomes zero, or clear one set bit at a time (Kernighan).

2 · intermediate

Shift n right until it is zero

time O(position of the highest set bit)space O(1)

Add the lowest bit (n & 1) to the count, shift n right by one, and repeat until n is zero.

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    while n != 0:
        count += n & 1
        n >>= 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    count += n & 1;
    n >>>= 1;
  }
  return count;
}

Flaws & bottlenecks

Still visits every position up to the highest set bit, including the zeros in between.
The number is modified (n is a copy, so the caller is safe, but the loop destroys the information).
A negative number (sign bit set) takes the full 32 iterations.

Interviewer cross-questions

When is this faster than the fixed loop?

Say: For small numbers: it stops at the highest set bit. For numbers with the top bit set it is no better.

What happens if the language shifts arithmetically?

Say: For a negative n, shifting right keeps filling with ones, so n never reaches 0 and the loop runs forever. Use an unsigned shift or an unsigned type.

Could n & 1 be replaced with n % 2?

Say: For non-negative n yes; for negative signed n the remainder can be negative, so the bit mask is safer.

3 · advanced

Brian Kernighan: clear the lowest set bit

time O(number of set bits)space O(1)

Replace n with n & (n − 1), which removes the lowest 1 bit, and count how many times that can be done before n becomes zero.

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    while n != 0:
        n = n & (n - 1)
        count += 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = (n & (n - 1)) >>> 0;
    count++;
  }
  return count;
}

Flaws & bottlenecks

The identity is a trick that must be known or derived.
Subtraction must not underflow: n − 1 for unsigned n = 0 is excluded by the loop condition.
Still a loop, so the cost depends on the input (up to 32 iterations).

Interviewer cross-questions

Why does n & (n − 1) clear the lowest set bit?

Say: Subtracting 1 borrows from the lowest 1: that bit becomes 0 and all the zeros below it become 1. The bits above are unchanged. AND-ing with n keeps the unchanged upper bits and zeroes everything from that bit down.

How else is the identity used?

Say: n & (n − 1) === 0 tests whether n is a power of two (or zero), and n & −n isolates the lowest set bit.

Which is better for dense numbers?

Say: For a number whose bits are almost all 1, Kernighan does up to 32 iterations, same as the plain loop. For sparse numbers it is much faster.

4 · expert

Parallel counting (SWAR)

time O(1) with about a dozen operationsspace O(1)

Count in parallel: turn each 2-bit field into its own population count, add neighbouring fields into 4-bit, then 8-bit counts, and gather the four byte counts with one multiplication. A fixed handful of operations, no loop and no branches.

int hammingWeight(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0f0f0f0f;
    return (n * 0x01010101u) >> 24;
}

public int hammingWeight(int n) {
    n = n - ((n >>> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
    n = (n + (n >>> 4)) & 0x0f0f0f0f;
    return (n * 0x01010101) >>> 24;
}

def hamming_weight(n):
    n = n - ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n + (n >> 4)) & 0x0f0f0f0f
    return ((n * 0x01010101) & 0xFFFFFFFF) >> 24

function hammingWeight(n: number): number {
  n = n - ((n >>> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
  n = (n + (n >>> 4)) & 0x0f0f0f0f;
  return Math.imul(n, 0x01010101) >>> 24;
}

Flaws & bottlenecks

The magic constants are hard to read and easy to mistype.
Written for exactly 32 bits; other widths need different constants.
Most hardware has a single-instruction popcount (__builtin_popcount, Integer.bitCount), which is faster and clearer: this is what those intrinsics fall back to.

Interviewer cross-questions

Why is each step correct?

Say: Step 1: for a two-bit field ab the count of ones is ab − a (two minus ... 00→0, 01→1, 10→1, 11→2). Steps 2 and 3 add neighbouring fields, and the masks stop carries from leaking into the next field; counts never exceed the field size, so no overflow occurs.

What does the multiplication by 0x01010101 do?

Say: It adds the four byte counts into the top byte (each byte is shifted and added to the others). Shifting right by 24 reads that top byte.

In production what would you write?

Say: The language's built-in: Integer.bitCount in Java, std::popcount or __builtin_popcount in C++, int.bit_count() in Python 3.10+. They compile to the CPU's popcount instruction.

Synchronized code walkthrough

Showing: Test each of the 32 positions — shares the player above; click any step to jump.

int hammingWeight(uint32_t n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n >> i) & 1) count++;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) != 0) count++;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    for i in range(32):
        if (n >> i) & 1: count += 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) count++;
  }
  return count;
}

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    while n != 0:
        count += n & 1
        n >>= 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    count += n & 1;
    n >>>= 1;
  }
  return count;
}

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

def hamming_weight(n):
    count = 0
    while n != 0:
        n = n & (n - 1)
        count += 1
    return count

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = (n & (n - 1)) >>> 0;
    count++;
  }
  return count;
}

int hammingWeight(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0f0f0f0f;
    return (n * 0x01010101u) >> 24;
}

public int hammingWeight(int n) {
    n = n - ((n >>> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
    n = (n + (n >>> 4)) & 0x0f0f0f0f;
    return (n * 0x01010101) >>> 24;
}

def hamming_weight(n):
    n = n - ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n + (n >> 4)) & 0x0f0f0f0f
    return ((n * 0x01010101) & 0xFFFFFFFF) >> 24

function hammingWeight(n: number): number {
  n = n - ((n >>> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
  n = (n + (n >>> 4)) & 0x0f0f0f0f;
  return Math.imul(n, 0x01010101) >>> 24;
}