Base Jumping

I ran into a little script a couple of months ago that completely baffled me. I knew what it did, but I couldn't figure out how.

#!/bin/bash
declare -i n=$1  
bin=  
while [[ $n != 0 ]]  
do  
    bin=$(( $n & 1 ))$bin
    (( n >>= 1 ))
done  
echo $bin  

This is Bash, but I am more familiar with Python, so for illustrative purposes:

#!/bin/python
from sys import argv  
n = int(argv[1])  
bin = []  
while n != 0:  
    bin.insert(0, (n & 1))
    n >>= 1      
print ''.join(map(str, bin))  

Not a whole lot of difference between the two, but I like the Python-isms that help clarify our methods. So what does this actually do?

This remarkably simple script will convert decimal integers to their binary representation all via bitwise operations. I'll try my best to break this down.

n = int(argv[1])  
bin = []  

First we store an argument that will be the number we wish to convert, and we intialize an empty array into which we will insert our 1's and 0's.

And here is the meat:

while n != 0:  
    bin.insert(0, (n & 1))
    n >>= 1

In C we would be dealing explicitly with the size of our integers in memory, but Python will abstract that away for us. Instead let's focus on the algorithm assuming a 4 bit integer.

For example, if we pass the integer 13 into our script:

13 is 1101 in base 2, knowing this we can see how this script can achieve the same result.

The first step in the while loop will look something like this:

1 1 0 1
0 0 0 1
----------- &
0 0 0 1 = 1

The bitwise & operator will perform a logical AND on each pair of bits, and the resulting bit will be 1 only if both bits are 1.

bin.insert(0, (n & 1))  

AND gate

Since 13 has a bit in the 1's place the & operation returns a 1 and this 1 gets inserted into our bin array at position 0 (the beginning or left most side).

Next, we shift the bits in our integer to the right:

n >>= 1  

The next iteration becomes:

0 1 1 0
0 0 0 1
----------- &
0 0 0 0 = 0

We insert the 0 into our bin array at position 0, which so far is: [01]

The next iteration:

0 0 1 1
0 0 0 1
----------- &
0 0 0 1 = 1

bin is now equal to: [101]

The last iteration:

0 0 0 1
0 0 0 1
----------- &
0 0 0 1 = 1

At this point the next right shift would assign our integer (n) to 0, which meets the conditional of the while loop and thus ends our bitwise operations. Our bin array's final value is [1101], and we can print this as a string to return the result in a readable format.