Converting integer to binary representation

[Bengt Richter]

On Tue, 16 Dec 2003 16:29:50 +0100, Mark Dufour <m.dufour at student.tudelft.nl> wrote:

>On Tuesday 16 December 2003 15:48, Fredrik Lundh wrote:
>> "Mark Dufour" <m.dufour at student.tudelft.nl> wrote:
>> > I need to convert an integer into some binary representation. I found the
>> > following code in the online cookbook (adapted to return a list):
>> >
>> > binary = lambda n: n>0 and [n&1]+binary(n>>1) or []
>> >
>> > This is sure nice, but I'm wondering why something like this doesn't seem
>> > to be in the standard library, for example by formatting with '%b' %
>> > number. I can't think of a any reason for not doing it this way, as
>> > working with binary representations is quite common in programming,
>>
>> really?  what kind of programs are you writing?
>
>I want to loop over the binary representation of numbers, for use in some 
>algorithm dealing with prime numbers. Of course, there are multiple ways of 
>doing this, but I like the clean: 'for power, bit in 
>enumerate(binary(number))', possible with the above code. 
>
>> (in my experience, binary numbers only appear in programming text
>> books.   humans tend to use decimal numbers, and programmers use
>> octal or hexadecimal numbers when they need to "access the bits").
>
>I've seen several attempts on the web for implementing this functionality in 
>Python, so I guess I'm not the only one needing or wanting it.. ;-) Some 
>programmers actually do work a lot with bits and prefer binary representation 
>sometimes, so why not add a simple provision to the language? Like, int() 
>takes a base argument, why not have str() take one as well?? If only just for 
>consistency :-)
>
Below is a class subclassing long to repr-show bits as bigendian strings and letting
you iterate through the bits from the little end. The values may be signed, with the
most significant bit being the sign bit (which logically extends left as far as you like),
and the literal form has a 'b' appended. This repr format "round-trips" -- i.e., you can
give it back to the constructor and get the same number.

(not tested beyond what you see here ;-)


====< lbits.py >================================================
class LBits(long):
    """
    Class acting like long, but showing bits for grins.
    2003-12-17 alpha version by Bengt Richter
    """
    class __metaclass__(type):
        """Wrap long methods to return LBits objects"""
        def __new__(cls, name, bases, cdict):
            exclude = [
                '__class__', '__cmp__', '__coerce__', '__delattr__',
                '__divmod__', '__doc__', '__float__', '__getattribute__', '__getnewargs__',
                '__hash__', '__hex__', '__init__', '__int__', '__invert__', '__long__',
                '__new__', '__nonzero__', '__oct__', '__pos__',
                '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__',
                '__rtruediv__', '__setattr__', '__str__', '__truediv__']
            for k, v in vars(long).items():
                if k in exclude: continue
                exec """\
def %s(self,*args,**kw):
    return self.__class__(long.%s(self,*args,**kw))
""" % (k, k) in cdict
            return type.__new__(cls, name, bases, cdict)
    def __new__(cls, v):
        """Handle additional string literal format with 'b' suffix and sign as leading bit"""
        if isinstance(v, str) and v[-1:].lower()=='b':
            if v[0]=='1':
                return long.__new__(cls, long(v[1:-1] or '0', 2)-(1L<<(len(v)-2)))
            else:
                return long.__new__(cls, v[1:-1] or '0', 2)
        return long.__new__(cls, v)
    def __repr__(self):
        """Show self in round-trip literal format, with leading bit as sign bit and 'b' suffix"""
        val = long(self)
        absval = abs(val)
        s=[chr(((val>>b)&1)+48) for b in xrange(len(hex(val))*4) if not b or absval>>(b-1)]
        s.reverse()
        return ''.join(s+['b'])
    def __iter__(self):
        """Return little-endian iterator through bits, including sign bit last"""
        return self.bitgen()
    def bitgen(self):
        """Little-endian bit sequence generator"""
        bits = long(self)
        sign = bits<0
        while bits>0 or sign and bits!=-1L:
            yield int(bits&1)
            bits >>= 1
        yield int(sign)
================================================================

 >>> from lbits import LBits
 >>> b = LBits(11)
 >>> b, -b, ~b, b&5, b^5, b*4, b/2, str(b), repr(b)
 (01011b, 10101b, -12L, 01b, 01110b, 0101100b, 0101b, '11', '01011b')
 >>> int(b), long(b), float(b), str(b), repr(b)
 (11, 11L, 11.0, '11', '01011b')
 >>> [bit for bit in b]
 [1, 1, 0, 1, 0]
 >>> [bit for bit in -b]
 [1, 0, 1, 0, 1]
 >>> print b,`b`,'str(b)=%s, repr(b)=%r'%(b,b)
 11 01011b str(b)=11, repr(b)=01011b
 >>> for i in xrange(-8,9):
 ...     print '%3s => %6r => %3s %s' %(i,LBits(i), LBits(repr(LBits(i))),[x for x in LBits(i)])
 ...
  -8 => 11000b =>  -8 [0, 0, 0, 1]
  -7 =>  1001b =>  -7 [1, 0, 0, 1]
  -6 =>  1010b =>  -6 [0, 1, 0, 1]
  -5 =>  1011b =>  -5 [1, 1, 0, 1]
  -4 =>  1100b =>  -4 [0, 0, 1]
  -3 =>   101b =>  -3 [1, 0, 1]
  -2 =>   110b =>  -2 [0, 1]
  -1 =>    11b =>  -1 [1]
   0 =>     0b =>   0 [0]
   1 =>    01b =>   1 [1, 0]
   2 =>   010b =>   2 [0, 1, 0]
   3 =>   011b =>   3 [1, 1, 0]
   4 =>  0100b =>   4 [0, 0, 1, 0]
   5 =>  0101b =>   5 [1, 0, 1, 0]
   6 =>  0110b =>   6 [0, 1, 1, 0]
   7 =>  0111b =>   7 [1, 1, 1, 0]
   8 => 01000b =>   8 [0, 0, 0, 1, 0]
 >>> [LBits(s) for s in '10b 1b 0b'.split()]
 [110b, 11b, 0b]
 >>> b
 01011b
 >>> sum([bit*2**pow for pow,bit in enumerate(b)])
 11
 >>> sum([bit*2**pow for pow,bit in enumerate(LBits(1023))])
 1023
(of course that sum has to be spelled an alternate way for negative numbers)

I wouldn't think it would be a big mod to get the current int and long to accept 'b'-suffixed
binary literals, BTW. And a %b in string formatting could work like LBits.__repr__ here. Maybe
with %b for lower case suffix and %B for upper case, to follow %x and %X usage. Obviously this
class is going to impose a performance hit over plain longs, but maybe it's useful to you?
I'll leave full testing and better error messages and adding a divmod method and such as an exercise ;-)

Regards,
Bengt Richter