Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note: - Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. - In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. `-3`.
Examples
Constraints
The input must be a binary string of length 32.
Approach
We can iterate 32 times (since it's a 32-bit integer). In each iteration, we check if the least significant bit (rightmost bit) is 1 using `n & 1`. If it is, we increment our count. Then, we shift `n` to the right by 1 bit. In Java, we must use the unsigned right shift operator `>>>` to avoid filling the leftmost bits with 1s when `n` is negative.
Complexity Analysis
Time complexity is O(1) because we always do a constant number of operations (up to 32 bits). Space complexity is O(1).
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { count += (n & 1); n >>>= 1; } return count; }}