Number of 1 Bits
Write a function that takes an unsigned integer as input and returns the number of 1 bits in the binary representation of the integer.
Constraints:
- The input integer is within the range [0, 4294967295].
- The function should run in O(log n) time complexity.
Examples:
Input: 11
Output: 3
Explanation: The binary representation of 11 is 1011, which has 3 bits that are 1.
Solutions
Bit Manipulation
Time: O(log n)Space: O(1)
The function uses bit manipulation to count the number of 1 bits in the binary representation of the input integer. It does this by using a while loop to iterate over each bit in the integer, and for each bit, it checks if the bit is 1 by using the bitwise AND operator (&) with 1. If the result is 1, it increments the count. The loop continues until all bits have been checked, at which point the function returns the count.
function hammingWeight(n) {
let count = 0;
while (n) {
count += n & 1;
n >>>= 1;
}
return count;
}
Follow-up:
How would you optimize the function to handle larger input integers?
