191. Number of 1 Bits

Today, I solved the Number of 1 Bits from Leetcode.

 

Description:

https://leetcode.com/problems/number-of-1-bits/description/

 

In this question, we are gonna work on changing the binary number to decimal numbers.

There are two methods to solve this problem in Python:

 

Solution1:

The first solution, we are gonna divide the number to see the first bit is 1 or 0. 

For example, 17 is 10001.

10001 % 2 = 1

 

Now, keep moving to the right!

1000 % 2 = 0

100 % 2 = 0

10 % 2 = 0

1 % 2 = 1

0 % 2 = 0 (at this point n is 0) --> while loop stop.

 

The result should be added in this order: 10000 + 0 + 0 + 0 + 1 = 17.

 

Solution2:

This is the second solution. It is a little bit different from the first solution.

Instead of moving to right, we are gonna do n & (n-1).

   10001 (17)

& 10000 (16)

-------------

    10000

& 01111

-------------

   00000 -> (n is 0)

 

In this algorithm, we can get the highest 1 bit.

Time Complexity: O(1)

Space Complexity: O(1)