🎨Now live: Try our Free AI Image Generation Feature

Description
The hammingWeight
function calculates the number of '1' bits in the binary representation of a given integer n
. This function is often referred to as the "population count" or "bit count".
Intuition
The intuition behind the hammingWeight
function is to repeatedly check the least significant bit of the integer and shift the integer to the right until all bits have been processed. By counting how many times the least significant bit is '1', we can determine the number of '1' bits in the binary representation of the integer.
Approach
- Initialize a counter
count
to zero. This counter will keep track of the number of '1' bits. - Use a loop to iterate over all bits in the integer
n
. - In each iteration, check if the least significant bit is '1' using the bitwise AND operation
n & 1
. If it is, increment thecount
. - Perform an unsigned right shift on the integer
n
to process the next bit. In Python, you can achieve this by using the expressionn >>= 1
. - Continue the loop until all bits have been processed (i.e., until
n
becomes zero). - Return the
count
as the result.
Complexity
Time Complexity:
O(1) - The function always processes 32 bits (for a 32-bit integer), so the time complexity is constant.
Space Complexity:
O(1) - The function uses a constant amount of space regardless of the input size.
Code
C++
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
};
Python
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
count += n & 1
n >>= 1
return count
Java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1; // unsigned right shift
}
return count;
}
}
JavaScript
/**
* @param {number} n
* @return {number}
*/
var hammingWeight = function (n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>>= 1;
}
return count;
};