191. Number of 1 Bits
easyCount the set bits in an unsigned integer. The textbook Brian Kernighan trick — n & (n - 1) drops the lowest set bit in O(set-bit-count) time.
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
n = 113Explanation: The input binary string 1011 has a total of three set bits.
Example 2
n = 1281Explanation: The input binary string 10000000 has a total of one set bit.
Example 3
n = 214748364530Explanation: 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.
Hints
Progressive — try the first before opening the next.
Hint 1
Naive: walk all 32 bits, count those set. O(32) time, fine but not slick.
Hint 2
Brian Kernighan's algorithm: n & (n - 1) clears the lowest set bit. Loop while n != 0: count++, n &= n - 1. Runs in O(set-bit-count) iterations.
Hint 3
Built-in option: most languages have popcount / bit_count. Always mention it but show your own implementation.
Hint 4
Divide-and-conquer SWAR trick: shift and mask to count bits in parallel in O(log 32) operations. Overkill for the interview but worth knowing.
Solution approach
Reveal approach
Brian Kernighan: maintain count = 0. While n != 0: count++; n &= n - 1. Return count. The bitwise AND n & (n - 1) drops the lowest set bit because n - 1 flips that bit to 0 and turns all lower zeros into ones; the AND keeps only the higher bits. So each iteration removes exactly one set bit, and the loop runs exactly popcount(n) times. O(set-bit-count) time, O(1) space — beats the naive 32-bit scan when only a few bits are set. Built-in alternative: many languages provide popcount / Integer.bitCount / __builtin_popcount — mention it but implement Kernighan to demonstrate the underlying idea.
Complexity
- Time
- O(1)
- Space
- O(1)
Related patterns
- bit-manipulation
- math
Related problems
- 338. Counting Bits
- 231. Power of Two
- 190. Reverse Bits
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Apple
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Number of 1 Bits and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →