Number of 1 Bits - Solution & Explanation
Problem Statement
Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).
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.
Constraints:
1 <= n <= 231 - 1
Follow up: If this function is called many times, how would you optimize it?
Approach Overview
Problem Overview: Given a 32-bit unsigned integer n, count how many bits are set to 1 in its binary representation. This count is often called the Hamming weight. The task focuses on efficient bit-level operations rather than converting the number to a string or using high-level utilities.
Approach 1: Iterative Bit Check (Time: O(32) ~ O(1), Space: O(1))
This method inspects each bit of the integer one by one. Use a loop while n > 0. Check the least significant bit with n & 1. If the result is 1, increment the counter. Then right-shift the number using n >> 1 to move the next bit into position. The algorithm performs at most 32 iterations for a 32-bit integer, so the runtime is effectively constant. This approach is straightforward and easy to implement during interviews when demonstrating basic bit manipulation skills.
Approach 2: Clear the Least Significant Set Bit using n & (n - 1) (Time: O(k), Space: O(1))
The expression n & (n - 1) removes the lowest set bit from a number. Each operation reduces the number of 1 bits by exactly one. Repeatedly apply this operation until n becomes 0, counting how many times it runs. If the integer contains k set bits, the loop runs exactly k times. This makes the algorithm faster when the number contains only a few set bits. The trick relies on binary arithmetic properties and is a classic technique in bit manipulation and divide and conquer-style bit reduction problems.
Recommended for interviews: Interviewers usually expect the n & (n - 1) solution. It demonstrates deeper understanding of binary representations and efficient bit tricks. The iterative bit check still shows solid fundamentals and is often a good first explanation. Moving from the basic bit scan to the optimized clearing trick signals strong problem-solving ability with low-level operations.
Approach 1: Approach 1: Iterative Bit Check
This approach involves iterating through each bit of the integer by continuously shifting the bits to the right and checking the least significant bit. Whenever the least significant bit is set, we increment our count. This continues until all bits have been checked.
This C code iteratively checks the least significant bit and uses the right shift operation to move the bits of the number. The Hamming weight is calculated by incrementing the count whenever the least significant bit is one. This process continues until all bits in the number have been checked.
Complexity
Time Complexity: O(b) where b is the number of bits in the integer.
Space Complexity: O(1) as no additional space is required.
Approach 2: Approach 2: Using n & (n - 1) to Clear Least Significant Set Bit
This approach leverages the property of bit manipulation where the operation n & (n - 1) results in the number with the lowest set bit turned off. By performing this operation iteratively, the loop proceeds directly to the next set bit, thus reducing the number of iterations required compared to shifting each bit position.
This C code uses the n & (n - 1) trick to clear the lowest set bit, effectively counting how many times we can perform this operation until the number is zero. Each operation reduces the number of set bits by one.
Complexity
Time Complexity: O(k) where k is the number of set bits.
Space Complexity: O(1) as no extra space is required.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Kotlin
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Bit Check | Time Complexity: O(b) where b is the number of bits in the integer. |
| Approach 2: Using n & (n - 1) to Clear Least Significant Set Bit | Time Complexity: O(k) where k is the number of set bits. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Bit Check | O(32) ≈ O(1) | O(1) | Simple implementation when scanning each bit is acceptable |
| n & (n - 1) Bit Clearing Trick | O(k) where k = number of set bits | O(1) | Preferred in interviews and optimized cases with few set bits |
Video Solution
Number of 1 Bits - Leetcode 191 - Python • NeetCode • 197,107 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of 1 Bits easy or hard?
Number of 1 Bits Python/Java solution
How to solve Number of 1 Bits in O(n)?
What is the best approach for Number of 1 Bits?
Is Number of 1 Bits asked at Google/Amazon/Meta?
What data structure is used in Number of 1 Bits?
What is the time complexity of Number of 1 Bits?
Ready to solve this problem?
Practice Number of 1 Bits with our built-in code editor and test cases.
Practice on FleetCode