Description
Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).
Examples:
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.Solution in Python
Python
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0 # Initialize the count of set bits to 0
# Loop until all bits in the integer are processed
while n:
# Use bitwise AND to check if the least significant bit (LSB) is set (1)
count += n & 1
# Right shift the integer by 1 bit to process the next bit in the next iteration
n >>= 1
return count # Return the total count of set bitsExplanation
- Initialization:
countis initialized to0. This variable will keep track of the number of set bits (i.e., bits that are1).
- Loop Through Bits:
- The
while nloop continues as long asnis not0. This ensures that we process each bit ofn.
- The
- Check Least Significant Bit:
- The expression
n & 1checks if the least significant bit (LSB) ofnis set (1). - If the LSB is
1, we incrementcountby1.
- The expression
- Shift Right:
- We then right shift
nby1bit usingn >>= 1. This effectively discards the LSB we just processed and moves the next bit into the LSB position for the next iteration.
- We then right shift
- Return the Result:
- After the loop,
countwill contain the total number of set bits in the binary representation ofn. This is returned as the result.
- After the loop,
Example
- For an input
n = 11:- Binary representation:
1011 - The loop processes each bit, finding that there are
3bits set to1. - The function returns
3.
- Binary representation:
- For an input
n = 128:- Binary representation:
10000000 - The loop finds
1bit set to1. - The function returns
1.
- Binary representation:
This solution efficiently calculates the Hamming weight with a time complexity of O(log n), where n is the number of bits in the integer.
Solution in Javascript
JavaScript
/**
* @param {number} n
* @return {number}
*/
var hammingWeight = function(n) {
let count = 0; // Initialize the count of set bits to 0
// Loop until all bits in the integer are processed
while (n !== 0) {
// Use bitwise AND to check if the least significant bit (LSB) is set (1)
count += n & 1;
// Right shift the integer by 1 bit to process the next bit in the next iteration
n = n >>> 1; // Use unsigned right shift to ensure correct handling of bits
}
return count; // Return the total count of set bits
};Solution in Java
Java
class Solution {
public int hammingWeight(int n) {
int count = 0; // Initialize the count of set bits to 0
// Loop until all bits in the integer are processed
while (n != 0) {
// Use bitwise AND to check if the least significant bit (LSB) is set (1)
count += n & 1;
// Right shift the integer by 1 bit to process the next bit in the next iteration
n >>>= 1; // Use unsigned right shift to ensure correct handling of bits
}
return count; // Return the total count of set bits
}
}Solution in C#
C#
public class Solution {
public int HammingWeight(int n) {
int count = 0; // Initialize the count of set bits to 0
// Loop until all bits in the integer are processed
while (n != 0) {
// Use bitwise AND to check if the least significant bit (LSB) is set (1)
count += n & 1;
// Right shift the integer by 1 bit to process the next bit in the next iteration
n = (int)((uint)n >> 1); // Use unsigned right shift to ensure correct handling of bits
}
return count; // Return the total count of set bits
}
}