Dare2Solve
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".
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.
count
to zero. This counter will keep track of the number of '1' bits.n
.n & 1
. If it is, increment the count
.n
to process the next bit. In Python, you can achieve this by using the expression n >>= 1
.n
becomes zero).count
as the result.O(1) - The function always processes 32 bits (for a 32-bit integer), so the time complexity is constant.
O(1) - The function uses a constant amount of space regardless of the input size.
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
};
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
count += n & 1
n >>= 1
return count
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;
}
}
/**
* @param {number} n
* @return {number}
*/
var hammingWeight = function (n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>>= 1;
}
return count;
};