[Tutor] Need help with binary notation

[Kirby Urner]

Lloyd Hugh Allen wrote:
>(this part's not so much for Jimmy): Clearly this can be done in a loop,
>where one first checks for zero and then takes the log base two of the
>number, perhaps holding the places that get a one in a list. To take log
>base two, do math.log(x)/math.log(2).


math.log is pretty intensive (slow) for this application.  Faster is
to just keep shift-lefting the decimal and grabbing the bits.  Since
the integer is already stored in binary, you don't need to recompute
anything, just convert it to a visible form e.g. a character string:

def base2(n,fill=0):
     """
     Convert a positive integer to base 2 string representation
     with optional 0-padding on left (2nd arg defines
     total width)
     """

     # screen for bogus input
     if n<0:
        # a better routine would accept negatives
        raise ValueError,"Must be positive"
     if type(n)<>type(1) and type(n)<>type(1L):
        raise ValueError,"Must be integer or long integer"

     outstr = ''
     while 1:
        if n&1: outstr = '%s%s' % ('1',outstr)
        else:   outstr = '%s%s' % ('0',outstr)
        n>>=1
        if n==0: break
     return string.zfill(outstr,fill)


 >>> base2(109019238)
'110011111111000000001100110'
 >>> base2(10)
'1010'
 >>> base2(2)
'10'
 >>> base2(1)
'1'
 >>> base2(0)
'0'

Kirby