LeetCode Meditations: Number of 1 Bits

Let’s start with the description this:

Given a positive integer nwrite a function that returns a set number of digits in binary representation (also known as Hamming weight).

For example:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

or:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

or:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

As we mentioned in the introductory chapter Previous articleone Set bit Refers to the bit with value 1.

So, what we have to do is count 1 digit.

One way is to convert the number to a string and then just count the 1’s. Alternatively, we can convert it to an array and filter out the 0’s, and get its length. However, there is another way to use bit operations.

We can delete set bits (bits with value 1) until the number becomes 0.

a good thing to know n - 1 yes The rightmost set of deleted versions of n.

For example, if n is 0010, n - 1 is 0001.

or if n Yes 0110, n - 1 Yes 0101.

We can create a loop that runs as long as there is 1 bit ncounting while walking.
And every time we can do one and Operation and n 1 less (n & (n - 1)).

A simple TypeScript solution looks like this:

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}

time and space complexity

I think the time complexity is

$O(log\n)$

— In the worst case, we will run the loop when all bits are set

$Log\n$

times (the number of digits in the binary representation of a number

$n$

Will

$Log\n$

).

The space complexity will be constant (

$Complexity(1)$

), since no additional memory usage increases as input increases.

The next question we have to consider is Count bit. Until then, happy coding.