LeetCode 191. Number of 1 Bits

Posted on Edited on In

Intuition

  • Check how many 1 bits are there in the binary representation of n.
  • Using the right shift operation, check whether the last bit of n is 1 (by checking whether n is odd).

Approach

  1. Initialise ans to 0.
  2. While n is greater than 0 (i.e., the binary representation contains at least one 1 bit):
    1. Increase ans if the last bit of n is odd (i.e., the binary representation of n is 1).

Pseudocode of hammingWeight():

1
2
3
4
5
6
7
8
9
10
hammingWeight(n):
	Input n a 32-bit unsigned integer
	Output number of 1 bits in the binary representation of n
	
	ans = 0
	while n > 0:
		ans += (n % 2)
		right shift n
	end while
	return ans

Complexity

  • Time complexity: $O(logn)$.

    • $logn$ iterations to calculate how many 1 bits are in the binary representation.

  • Space complexity: $O(1)$.

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
  int hammingWeight(uint32_t n) {
    int ans = 0;
    while (n > 0) {
      ans += (n % 2);
      n >>= 1;
    }
    return ans;
  }
};