Number of 1 Bits easy

Problem Statement

Write a function that takes an unsigned integer as input and returns the number of 1 bits (also known as set bits or Hamming weight) in its binary representation.

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 1 bits, initialized to 0.
  2. Iterate through bits: Iterate through the bits of the input 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 the counter: If the least significant bit is 1, increment the count.
  5. Right-shift the integer: 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 the count: Return the final value of count.

Explanation

The algorithm efficiently counts set bits by repeatedly checking and removing the least significant bit. The bitwise AND operation isolates the least significant bit, and the right-shift operation moves the next bit into the least significant position for the next iteration. This continues until all bits have been checked.

Code

function hammingWeight(n: number): number {
    let count = 0;
    while (n > 0) {
        count += n & 1; //Check the least significant bit
        n >>= 1;       //Right-shift n by 1
    }
    return count;
};

Complexity

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