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 - 1The goal of #191 Number of 1 Bits is to count how many 1 bits (also called set bits) appear in the binary representation of a given integer. This is a classic bit manipulation problem frequently asked in coding interviews.
A straightforward idea is to repeatedly inspect the least significant bit using a bitwise operation like n & 1. After checking, shift the number to the right using n >> 1 until all bits are processed. Each step tells you whether the current bit contributes to the count.
A more optimized approach uses the trick n & (n - 1), which removes the lowest set bit in each iteration. By repeatedly applying this operation, the loop runs only as many times as there are 1 bits in the number. This makes the method very efficient when the number contains few set bits.
Both approaches rely on understanding how binary numbers behave under bitwise operations, a key concept in many low-level and performance-focused problems.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit Shift and Check (n & 1) | O(32) or O(log n) | O(1) |
| Brian Kernighan’s Algorithm (n & (n-1)) | O(k), where k is the number of set bits | O(1) |
NeetCode
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.
Time Complexity: O(b) where b is the number of bits in the integer.
Space Complexity: O(1) as no additional space is required.
1function hammingWeight(n) {
2 let count = 0;
3 while (n !== 0) {
4 count += n & 1;
The JavaScript function computes the count of set bits in an integer using the bitwise AND to identify set bits and the `>>>` unsigned right shift to iterate through each bit position.
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.
Time Complexity: O(k) where k is the number of set bits.
Space Complexity: O(1) as no extra space is required.
1using namespace std;
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
int main() {
cout << hammingWeight(11) << endl; // Output: 3
cout << hammingWeight(128) << endl; // Output: 1
cout << hammingWeight(2147483645) << endl; // Output: 30
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Number of 1 Bits problem appear in interviews at major tech companies. It is often used to evaluate a candidate’s understanding of bit manipulation and their ability to write efficient low-level logic.
No special data structure is required for this problem. The solution relies purely on integer variables and bitwise operations to analyze the binary representation of the number.
A widely used optimal method is Brian Kernighan’s algorithm. It repeatedly applies the operation n & (n - 1) to remove the lowest set bit until the number becomes zero. The number of iterations equals the number of 1 bits, making it efficient when the integer has few set bits.
This problem mainly tests bit manipulation fundamentals. Candidates must understand how binary numbers work and how bitwise operators like AND and bit shifts can be used to inspect and modify individual bits.
This C++ solution optimizes the counting of set bits by iteratively turning off the lowest set bit until the integer becomes zero, counting the number of operations performed.