How do you solve Number of 1 Bits?

Use Brian Kernighan’s algorithm: repeatedly apply n &= (n - 1) to clear the rightmost set bit and increment a counter until n becomes zero. This approach counts only the set bits, resulting in a time complexity proportional to the number of '1's rather than the total number of bits.

Number of 1 Bits

Q: What is the time complexity of Number of 1 Bits?

O(m). Each iteration removes one set bit from n, so the loop runs exactly as many times as there are '1' bits in n.

Q: What pattern does Number of 1 Bits use?

The Pattern: Bit Manipulation (Brian Kernighan’s Algorithm for Counting Set Bits) The Heuristic: The operation n & (n - 1) removes the rightmost set bit, enabling a loop that runs exactly as many times as there are set bits, making counting bits efficient and elegant.

Easy Bit Manipulation

Problem

Given an unsigned integer n, return the number of '1' bits it has (also known as the Hamming weight).

The input must be treated as an unsigned integer.
The number of bits in n can be up to 32 or 64 depending on the system.

Example

Input: n = 11

Output: 3

The binary representation of 11 is 1011, which contains three '1' bits. The algorithm repeatedly removes the rightmost set bit from n by performing n &= (n - 1), incrementing a counter each time until n becomes zero. This efficiently counts all set bits without checking each bit individually.

Approach

Straightforward Solution

A naive approach checks each bit individually by shifting and masking, resulting in O(k) time where k is the number of bits (e.g., 32 or 64). This is simple but not optimal.

Core Observation

Each '1' bit in the binary representation corresponds to a set bit. The operation n & (n - 1) removes the rightmost set bit from n, reducing the number of set bits by one each time it is applied.

Path to Optimal

Preview

The key recognition signals are 'count number of set bits' and 'bitwise operations'. These indicate Bit Manipulation because the problem can be solved by exploiting properties of binary numbers…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use Brian Kernighan’s algorithm: repeatedly apply n &= (n - 1) to clear the rightmost set bit and increment a counter until n becomes zero…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m)

Each iteration removes one set bit from n, so the loop runs exactly as many times as there are '1' bits in n.

Space

O(1)

Only a fixed number of variables are used (res and n), so the auxiliary space is constant regardless of input size.

Pattern Spotlight

Bit Manipulation (Brian Kernighan’s Algorithm for Counting Set Bits)

The operation n & (n - 1) removes the rightmost set bit, enabling a loop that runs exactly as many times as there are set bits, making counting bits efficient and elegant.

Solution

Python

1class Solution:
  def hammingWeight(self, n: int) -> int:
      res = 0
      while n:
          n &= (n - 1)
          res += 1
      return res

Step-by-Step Solution

Count Set Bits by Clearing Rightmost Set Bit Iteratively

3res = 0
4while n:
5    n &= (n - 1)
6    res += 1
7return res

Objective

To count the number of '1' bits by repeatedly removing the rightmost set bit until the number becomes zero.

Key Insight

The operation n &= (n - 1) efficiently clears the rightmost set bit in each iteration, reducing the problem size by one set bit at a time. This avoids checking every bit individually and leads to a loop that runs only as many times as there are set bits, which is often much faster than scanning all bits.

Interview Quick-Check

Core Logic

Using n &= (n - 1) removes the rightmost set bit, so the loop executes exactly once per set bit, making the count efficient.

State & Boundaries

The loop continues while n is non-zero, ensuring all set bits are counted.

Common Pitfalls & Bugs

A common mistake is to iterate over all bits using shifts, which is less efficient when the number of set bits is small.

Complexity

The time complexity depends on the number of set bits, not the total bit length, which can be a significant optimization.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 5 Critical

n &= (n - 1)

Remove the rightmost set bit from n using bitwise AND with n - 1.

This operation exploits binary arithmetic properties to clear the least significant '1' bit, reducing the problem size efficiently without examining each bit individually.

Line 6 Critical

res += 1

Increment the counter for each removed set bit.

Each iteration corresponds to removing exactly one set bit, so incrementing the counter here accurately counts the total number of '1' bits.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why does the operation n &= (n - 1) remove the rightmost set bit from n?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Number of 1 Bits from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Number of 1 Bits drill

or drill a free problem

1	`class Solution:`
2	`def hammingWeight(self, n: int) -> int:`
3	`res = 0`
4	`while n:`
5	`n &= (n - 1)`
6	`res += 1`
7	`return res`

3	`res = 0`
4	`while n:`
5	`n &= (n - 1)`
6	`res += 1`
7	`return res`