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 - 1Follow up: If this function is called many times, how would you optimize it?
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(b) where b is the number of bits in the integer.
Space Complexity: O(1) as no additional space is required.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(k) where k is the number of set bits.
Space Complexity: O(1) as no extra space is required.
| 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. |
| 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 |
Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 159,560 views views
Watch 9 more video solutions →Practice Number of 1 Bits with our built-in code editor and test cases.
Practice on FleetCode