DEV Community

Cover image for LeetCode Meditations: Number of 1 Bits
Eda
Eda

Posted on • Originally published at rivea0.github.io

LeetCode Meditations: Number of 1 Bits

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.
Enter fullscreen mode Exit fullscreen mode

Or:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.
Enter fullscreen mode Exit fullscreen mode

Or:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Enter fullscreen mode Exit fullscreen mode

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.
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;
}
Enter fullscreen mode Exit fullscreen mode
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(log n)O(log \ n) — In the worst case when all bits are set, we'll run through the loop log nlog \ n times (the number of bits in the binary representation of a number nn will be log nlog \ 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.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

typescript

11 Tips That Make You a Better Typescript Programmer

1 Think in {Set}

Type is an everyday concept to programmers, but it’s surprisingly difficult to define it succinctly. I find it helpful to use Set as a conceptual model instead.

#2 Understand declared type and narrowed type

One extremely powerful typescript feature is automatic type narrowing based on control flow. This means a variable has two types associated with it at any specific point of code location: a declaration type and a narrowed type.

#3 Use discriminated union instead of optional fields

...

Read the whole post now!

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay