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:
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:
When we ask Python to right shift 5, python will do this operation in binary:
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:
Understanding that anything that is not zero is True in boolean
You need to know this because our while loop will exit when we keep right shifting 5 and its value reaches 0.
Our Code
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:
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:
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
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:
so counter is now whatever it was (0) plus 1, so counter = 1.
Next, we shift number variable (currently 5) by 1:
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:
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:
Now we've got the following:
counter = 1
number = 1
The first operation will be number (1) & 1 or 0001 & 0001 in binary:
so counter is now whatever it was (1) plus 1, so counter is now 2.
We shift number again (currently 1) by 1:
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:
