Number of 1 Bits
Problem Description
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?
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
Counting the number of 1 bits in an integer can be approached by iterating through each bit and checking whether it is 1. This can be efficiently done by using bit shifts.
Steps:
- Initialize a counter to keep track of the number of 1 bits.
- Use a loop to iterate over each of the 32 bits of the integer.
- Use a bitmask to isolate each bit and determine if it's 1.
- For each bit that is 1, increment the counter.
- Return the counter as the result.
Code:
- Time Complexity: O(32) = O(1): Since the integer is a fixed 32-bit value.
- Space Complexity: O(1): Only constant space is used.
2. Bit Manipulation
Intuition:
The brute force approach can be optimized by using a clever trick with bit manipulation. By repeatedly turning off the rightmost 1-bit, we can directly count the 1-bits without checking each individual bit.
Doing n & (n - 1) removes the rightmost 1-bit from n.
Why?
- Subtracting 1 flips the lowest 1-bit to 0 and turns all bits to its right into 1s.
- AND-ing the result with the original number clears exactly that lowest 1-bit.
Each application of this operation removes one set bit. So if we repeat this process and count how many times it happens, the count equals the number of 1-bits.
This allows us to skip all zero bits and only operate on actual 1-bits making it much faster than a brute force bit scan.
Example Walkthrough
Let’s count the 1-bits in: n = 13 → binary: 1101
Steps:
- Initialize a counter to track the number of 1 bits.
- Loop while
nis not zero. - Apply
n = n & (n - 1)to turn off the lowest 1-bit. - Increment the counter.
- When all 1-bits are removed and
nbecomes zero, return the counter.
Code:
- Time Complexity: O(k): k is the number of 1-bits in the integer. In the worst case, k can be up to 32 for a 32-bit integer.
- Space Complexity: O(1): Only constant space is used.