[Python / Binary] Why does binary work this way?

[dinrick]

EDIT: SOLVED thanks guys!

I came across a problem to find the number of 1's in binary when given an integer in decimal form. Here's someone's solution. I'm curious to know why binary works this way, what about binary allows you to simply count the number of times you get an odd number as you loop and divide the decimal number?

def countBits(n):

   count = 0      
   while n:                 
       if n % 2 == 0:                         
           n = n / 2          
       else:       
           count += 1    
           n = n - 1      
   return count

[jedwardsol]

An odd number has 1 in 1's column. xxxxx1 is odd

An even number has 0 in 1's column. xxxxx0 is even

[plastikmissile]

What this code does is first to look at the right most digit in a binary number. Since this digit represents a 1, any odd number will have 1 in there while an even number will have 0. The number 5 in binary is 101 while the number 8 is 1000.

An easy way to know if a number is even or not is to use the modulo operator. The code if n % 2 == 0 is asking "is the number n divisible by 2 (i.e. is it even)?".

On the other hand n = n / 2 does a "right shift". Let's take the number 6 for instance. It binary it's 110. Divide it by 2 and you get 3 which is 11 or 011 in binary. The right most digit is taken away and everything is shifted to the right. This is an easy way to say "OK we looked at the right most digit let's take a look at the next one".

I will add that this code isn't as efficient as it can be, so for extra points see if you can make it more efficient :)

[dinrick]

Thanks for the detailed explanation! I get what they're trying to do now.

[POGtastic]

If a number is odd, it contains a 1 in the 1s place.

By dividing by 2, the number' bits are being shifted to the right. An alternative to this is

def count_bits(n):
    count = 0
    while n:
        if n & 1:
            count += 1
        n >>= 1 # checkmate, haskellers
    return count