1 x 2^7 + 1 x 2^6 + 1 x 2^5 + 0 x 2^4 + 1 x 2^3 + 0 x 2^2 + 0 x 2^1 + 1 x 2^0
A simple algorithm for finding the base 2 representation of a base 10 number is the following: repeatedly divide the decimal number by 2 and keep track of the remainder. The first division by 2 tells whether the number is even or odd. An even value will have a remainder of 0 and therefore a 0 in the ones place. The division process for converting 233 is shown below:233// 2 = 116 rem 1
116 // 2 = 58 rem 0
58 // 2 = 29 rem = 0
29 // 2 = 14 rem = 1
14 // 2 = 7 rem 0
7 // 2 = 3 rem = 1
3 // 2 = 1 rem = 1
1 // 2 = 0 rem = 1
Note that the first remainder computed is actually the last digit in the sequence. In other words, the digits are produced in the reverse order of their written sequence, which makes a stack perfectly suited to storing the remainders throughout this iterative process.
Use a stack as auxillary storage in your solution. The Stack class is shown below for reference:
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
return self._items.pop()
def is_empty(self):
return self._items == []
def __str__(self):
return str(self._items)