Problem
You are given a positive integern. Return the number of 1 bits in its binary representation. A set bit is a bit whose value is 1. This is also known as the Hamming Weight of the number.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 11Output
3Solution
We can solve this problem using a bit manipulation technique. The expressionn & (n - 1) removes the rightmost set bit from n.
For example, consider
n = 12:
n = 1100
n - 1 = 1011
n & (n - 1) = 10001 has been removed.
Therefore, we repeatedly apply
n & (n - 1) and increment the count until n becomes 0. The number of iterations is equal to the number of set bits.
class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
// Remove the rightmost set bit.
n = n & (n - 1);
count++;
}
return count;
}
}
The bitwise & (AND) operator compares two numbers bit by bit in their binary representation. For each position, the result is 1 only when both numbers have a 1 at that position. If either number has a 0, the result is 0.
Subtracting 1 from a binary number changes its rightmost set bit (1) to 0 and changes all trailing 0s after it to 1s.
Therefore, when we perform n & (n - 1), the rightmost set bit of n is cleared to 0, while all higher bits remain unchanged.
Complexity
The loop runs once for every set bit, so if there arek set bits, the time complexity is O(k), which is O(1) for a fixed-size 32-bit integer.
Only a constant number of variables is used, resulting in
O(1) space complexity.