Number of 1 Bits easy

Problem Statement

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Steps

  1. Initialize a counter: Create a variable count to store the number of 1s, initialized to 0.
  2. Iterate through bits: Loop through the bits of the integer n. We can do this using a while loop and bitwise operations.
  3. Check the least significant bit: Use the bitwise AND operator (&) to check if the least significant bit is 1. n & 1 will result in 1 if the least significant bit is 1, and 0 otherwise.
  4. Increment counter: If the least significant bit is 1, increment count.
  5. Right shift: Use the right shift operator (>>) to shift the bits of n one position to the right. This effectively removes the least significant bit.
  6. Repeat: Continue steps 3-5 until n becomes 0.
  7. Return count: After the loop finishes, return the value of count.

Explanation

The solution leverages bit manipulation for efficiency. The bitwise AND operation (&) isolates the least significant bit. The right shift operator (>>) efficiently moves to the next bit. This avoids the need for string conversion or other less efficient methods. The loop continues until all bits have been examined.

Code

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;
        }
        return count;
    }
}

Complexity

  • Time Complexity: O(log n), where n is the input integer. The number of iterations in the while loop is proportional to the number of bits in n (which is logâ‚‚n).
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.