cancel
Showing results for 
Search instead for 
Did you mean: 

Things to Keep in Mind

  • Most significant bit: left-most bit
  • Least significant bit: right-most bit
  • Think of Python reading your decimal number in its binary form under the hood

Understanding the Trick to Check if Last Bit is 1

The & operator returns 1 every time 1 is also compared to 1 and zero for 1 compared to anything else:

0151T000003kvzhQAA.png

Keep this in mind as we're going to use it in our code.

Right and Left Shift Operators in Python

Let's take decimal 5 as our example.

5 in binary is 0101:

0151T000003kvziQAA.png

When we ask Python to right shift 5, python will do this operation in binary:

0151T000003kvzwQAA.png

The above is the same as moving 0101 (5 in decimal) to the right so it's now 0010 (2 in decimal).

If you move 2 one bit to the left it's 4 because when we move the one from 0010 it's now 0100: 

0151T000003kw0LQAQ.png

Understanding that anything that is not zero is True in boolean

0151T000003kw0QQAQ.png

You need to know this because our while loop will exit when we keep right shifting 5 and its value reaches 0.

Our Code

0151T000003kw0VQAQ.png

What does above code do

Our little code here will count the number of binary 1's given a decimal number as input using right shift operation previously described.

Our while loop ends when number = 0 and counter variable increments every time least significant bit = 1. Easy eh?

Let's use 5 as an example. A better way to understand it is to think of our code like this:

0151T000003kw0aQAA.png

After we discard "1", we repeat the above with 0010 and so on, until we number = 0.

Running our Code

Let's run it but we already know that the number of 1's in 5 (0101 in binary) is 2:

0151T000003kw0fQAA.png

In case you didn't understand yet you can follow along the bonus section with step by step explanation about the code.

BONUS! Going through our Code Step by Step

0151T000003kw0kQAA.png

counter variable starts at 0 and we enter the while loop as variable number (5) is not yet zero.

counter = 0

number = 5

The first operation will be number (5) & 1 or 0101 & 0001 in binary:

0151T000003kw0pQAA.png

so counter is now whatever it was (0) plus 1, so counter = 1.

Next, we shift number variable (currently 5) by 1:

0151T000003kw19QAA.png

We now come back to our while loop again and because number is still not zero yet we keep going.

counter = 1

number = 2

The first operation will be number (2) & 1 or 0010 & 0001 in binary:

0151T000003kw1EQAQ.png

so counter is now whatever it was (1) plus 0, so counter does not change (still 1).

Next, we shift number again (currently 2) by 1:

0151T000003kw1JQAQ.png

Now we've got the following:

counter = 1

number = 1

The first operation will be number (1) & 1 or 0001 & 0001 in binary:

0151T000003kw1KQAQ.png

so counter is now whatever it was (1) plus 1, so counter is now 2.

We shift number again (currently 1) by 1:

0151T000003kw1OQAQ.png

We come back to our while loop again but this time we exit because number is now 0 and we return counter (2).

This is the result our code again:

0151T000003kw1TQAQ.png

Version history
Last update:
‎29-Aug-2019 04:32
Updated by:
Contributors