Skip to main content

191. Number of 1 Bits

easy

Count the number of set bits (popcount / Hamming weight) of a 32-bit unsigned integer. The textbook bit-twiddle: n & (n - 1) clears the lowest set bit.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Constraints

  • 1 <= n <= 2^31 - 1

Examples

Example 1

Input
n = 11
Output
3

Explanation: The input binary string 1011 has a total of three set bits.

Example 2

Input
n = 128
Output
1

Explanation: The input binary string 10000000 has a total of one set bit.

Example 3

Input
n = 2147483645
Output
30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive loop tests each of the 32 bits with n & 1 then right-shifts.

Hint 2

Brian Kernighan's trick: n & (n - 1) clears the lowest set bit of n. Count how many times you can do this before n becomes 0.

Hint 3

The Kernighan loop runs once per set bit instead of once per bit position — much faster when the input is sparse.

Solution approach

Reveal approach

Brian Kernighan's algorithm. Initialize count = 0. While n != 0, do n = n & (n - 1) and increment count. The expression n & (n - 1) flips the lowest set bit of n to zero (subtracting 1 turns the lowest 1 into a 0 and all trailing 0s into 1s; the AND wipes that whole run). The loop terminates as soon as no set bits remain. Time is O(k) where k is the number of set bits — at most 32 for the constraint range. Space is O(1).

Complexity

Time
O(k) where k = popcount(n)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Number of 1 Bits and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →