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.
public
class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}
}Follow-up:
How would you optimize the function to handle larger input integers?
