Number of 1 Bits
EasyPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward approach where we iterate through each of the 32 bits of the integer. In each iteration, we check if the current bit is a '1' and shift the number to the right to process the next bit.
Algorithm
- Initialize a counter
countto zero. - Loop 32 times, as we are dealing with 32-bit integers.
- Inside the loop, use a bitmask
1to check the least significant bit (LSB) of the numbern. The expression(n & 1)will be1if the LSB is1, and0otherwise. - Add the result of this check to
count. - Right-shift the number
nby one position (n >>= 1) to move the next bit into the LSB position for the next iteration. - After 32 iterations,
countwill hold the total number of set bits.
Walkthrough
This approach iterates through all 32 bits of the integer. The algorithm is as follows:
- Initialize a counter
countto zero. - Loop 32 times. In each iteration, we check the least significant bit (LSB).
- The check is done using a bitwise AND with 1:
(n & 1). If the result is 1, it means the LSB is a set bit, and we incrementcount. - After checking the bit, we shift the number
none position to the right (n >>= 1) to expose the next bit at the LSB position for the subsequent iteration. - After the loop completes,
countholds the total number of set bits.
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { if ((n & 1) == 1) { count++; } // Using unsigned right shift is safer for negative numbers, // but for the given constraints (positive n), >> is fine. n = n >> 1; } return count; }}Complexity
Time
O(k), where k is the number of bits in the integer (e.g., 32). Since k is a constant, this is technically O(1), but it performs a fixed number of iterations regardless of the input's properties.
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Cons
Performs a fixed number of iterations (32), which is inefficient for numbers with few set bits (e.g., n=1).
This approach uses a clever bit manipulation trick, n & (n - 1), which has the property of unsetting the rightmost '1' bit of a number. We can repeatedly apply this operation and count how many times it takes for the number to become zero. This count equals the number of set bits.
Algorithm
- Initialize
count = 0. - Start a loop that continues as long as
nis not equal to 0. - Inside the loop, apply the operation
n = n & (n - 1)to unset the rightmost set bit. - Increment the
countin each iteration. - Once
nbecomes 0, returncount.
Walkthrough
This highly efficient method relies on a specific bitwise operation: n & (n - 1).
This operation cleverly unsets (turns off) the rightmost '1' bit in a number. Let's see how:
- When we subtract 1 from a number
n, all the bits from the rightmost '1' to the LSB are flipped. - For example, if
n = 12(binary1100), thenn - 1 = 11(binary1011). - Performing a bitwise AND (
&) betweennandn - 1will make the rightmost '1' and all bits to its right zero.1100 & 1011results in1000.
The algorithm repeatedly applies this trick until the number becomes 0. The number of times we perform the operation is exactly the number of set bits.
public class Solution { public int hammingWeight(int n) { int count = 0; while (n != 0) { // This operation unsets the rightmost set bit n = n & (n - 1); count++; } return count; }}Complexity
Time
O(m), where m is the number of set bits. This is highly efficient as the number of loop iterations is equal to the number of set bits, which is often much smaller than the total number of bits (32).
Space
O(1)
Trade-offs
Pros
Very efficient, as the number of iterations equals the number of set bits.
Cons
The logic of
n & (n - 1)can be less intuitive for beginners.
This approach addresses the follow-up question: 'If this function is called many times, how would you optimize it?'. It involves pre-calculating the number of set bits for a smaller range of numbers (e.g., all 8-bit numbers) and storing them in a lookup table. A 32-bit integer is then processed by breaking it into four 8-bit chunks, looking up the count for each, and summing them up.
Algorithm
Preprocessing:
- Create a table
cacheof size 256. - For each
ifrom 0 to 255, calculate its Hamming weight and store it incache[i].
Query:
- Given an integer
n. - Extract the four 8-bit chunks of
nusing bitwise AND and shifts. - Return the sum of the cached Hamming weights for each of the four chunks.
Walkthrough
This method, ideal for the follow-up question, trades space for time. It's extremely fast when the function is called frequently.
1. Preprocessing (One-time Setup) First, we precompute the number of set bits for all possible 8-bit numbers (0 to 255) and store them in a lookup table (an array).
2. Querying (Per Call)
For any given 32-bit integer n, we can view it as four separate 8-bit chunks (bytes). We find the number of set bits in each chunk by looking up our precomputed table. The total count is the sum of the counts for these four chunks.
We can extract each 8-bit chunk using bitwise operations:
n & 0xff: Extracts the first byte (bits 0-7).(n >> 8) & 0xff: Extracts the second byte (bits 8-15).(n >> 16) & 0xff: Extracts the third byte (bits 16-23).(n >> 24) & 0xff: Extracts the fourth byte (bits 24-31).
public class Solution { // A static lookup table to store bit counts for numbers 0-255. private static final int[] BITS_IN_BYTE = new int[256]; // A static initializer block to populate the table when the class is loaded. static { for (int i = 0; i < 256; i++) { // Using Brian Kernighan's algorithm to populate the table. int count = 0; int n = i; while (n != 0) { n &= (n - 1); count++; } BITS_IN_BYTE[i] = count; } } public int hammingWeight(int n) { // Sum the bit counts of the four bytes of the integer. return BITS_IN_BYTE[n & 0xff] + BITS_IN_BYTE[(n >> 8) & 0xff] + BITS_IN_BYTE[(n >> 16) & 0xff] + BITS_IN_BYTE[(n >> 24) & 0xff]; }}Complexity
Time
O(1) per query, after a one-time preprocessing cost of O(L), where L is the size of the lookup table (e.g., 256).
Space
O(L), where L is the size of the lookup table (e.g., 256).
Trade-offs
Pros
Extremely fast for repeated calls, achieving constant time performance per query.
Cons
Requires extra space for the lookup table.
Incurs a one-time setup cost for preprocessing.
Solutions
Solution
public class Solution { // you need to treat n as an unsigned value public int hammingWeight ( int n ) { int ans = 0 ; while ( n != 0 ) { n &= n - 1 ; ++ ans ; } return ans ; } }/** * @param {number} n - a positive integer * @return {number} */ var hammingWeight = function (n) { let ans = 0; while (n) { n &= n - 1; ++ans; } return ans; };class Solution: def hammingWeight(self, n: int) -> int: ans = 0 while n: n &= n - 1 ans += 1 return ansclass Solution {public: int hammingWeight(uint32_t n) { int ans = 0; while (n) { n &= n - 1; ++ans; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.