LeetCode Meditations: Number of its

Let's start with the description for this one:

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the 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 chapter introduction in the previous post, a set bit refers to a bit with the value of 1.

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

One way to do it is to convert the number to a string, and just count the 1s. Or, we can convert that to an array and filter out the 0s, and get its length. But, there is another approach where we can use bit manipulation.

We can remove the set bits (bits that have the value 1) until the number becomes 0.

A good thing to know is that n - 1 is the rightmost set removed version of n.

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

Or, if n is 0110, n - 1 is 0101.

Note

It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.

Note

It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.
For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000.
Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000. Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

We can create a loop that runs as long as there are 1 bits in n, counting each one as we go. Also each time, we can do an AND

operation with n and 1 less of it (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;
}

Note

We are using the bitwise AND assignment operator to assign the value to n.

Time and space complexity

The time complexity is, I think, $O(logn)$O(log n) — In the worst case when all bits are set, we'll run through the loop $logn$log n times (the number of bits in the binary representation of a number $n$n will be $logn$log n ).

The space complexity will be constant ( $O(1)$O(1) ) as there is no additional memory usage that will increase as the input increases.

---

The next problem we'll take a look at is Counting Bits. Until then, happy coding.

The above is the detailed content of LeetCode Meditations: Number of its. For more information, please follow other related articles on the PHP Chinese website!