Base-2 (binary) representation using Python

Question

Based on How do you express binary literals in Python , I thought of reasonable, intuitive ways to do this programming 101 chestnut integer-based base-2 forms. This is the best I came up with, but I would like to replace it with a better algorithm, or at least least one that should have flashy performance.

def num_bin(N, places=8): def bit_at_p(N, p): ''' find the bit at place p for number n ''' two_p = 1 << p # 2 ^ p, using bitshift, will have exactly one # bit set, at place p x = N & two_p # binary composition, will be one where *both* numbers # have a 1 at that bit. this can only happen # at position p. will yield two_p if N has a 1 at # bit p return int(x > 0) bits = ( bit_at_p(N,x) for x in xrange(places)) return "".join( (str(x) for x in bits) ) # or, more consisely # return "".join([str(int((N & 1 << x)>0)) for x in xrange(places)]) 

Answer 1

For best performance, you usually want to process more than one bit at a time. You can use a simple method to get a fixed width binary representation. eg.

 def _bin(x, width): return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1)) 

_bin (x, 8) will now give a zero padded representation x of the lower 8 bits. This can be used to build a lookup table, which allows the converter to process 8 bits at a time (or more if you want to dedicate memory to it).

 _conv_table = [_bin(x,8) for x in range(256)] 

You can then use this in your real function by discarding leading zeros on return. I also added the processing of signed numbers, since without it you would get an infinite loop (negative integers conceptually have an infinite number of bits of the dial sign.)

 def bin(x): if x == 0: return '0' #Special case: Don't strip leading zero if no other digits elif x < 0: sign='-' x*=-1 else: sign = '' l=[] while x: l.append(_conv_table[x & 0xff]) x >>= 8 return sign + ''.join(reversed(l)).lstrip("0") 

[Edit] Changed code for handling signed integers.
[Edit2] Here are some timelines for various solutions. bin is the function above, constantin_bin is Konstantin's answer , and num_bin is the original version. Out of curiosity, I also tried a variant of the 16-bit lookup table above (bin16 below) and tried out the Python3 built-in bin () function. All timings were performed for 100,000 runs using the bit pattern 01010101.

 Num Bits: 8 16 32 64 128 256 --------------------------------------------------------------------- bin 0.544 0.586 0.744 1.942 1.854 3.357 bin16 0.542 0.494 0.592 0.773 1.150 1.886 constantin_bin 2.238 3.803 7.794 17.869 34.636 94.799 num_bin 3.712 5.693 12.086 32.566 67.523 128.565 Python3 bin 0.079 0.045 0.062 0.069 0.212 0.201 

As you can see, when processing long values ​​using large fragments, it really pays off, but nothing beats the python3 builtin low-level C code (which strangely seems to be consistently faster by 256 bits than 128!). Using a 16-bit lookup table improves the situation, but it's probably not worth it if you really don't need it, because it uses a large chunk of memory and may introduce a small but note-delayed launch to precompile the table.

Answer 2

Do not scream - quickly, but simply:

 >>> def bin(x): ... sign = '-' if x < 0 else '' ... x = abs(x) ... bits = [] ... while x: ... x, rmost = divmod(x, 2) ... bits.append(rmost) ... return sign + ''.join(str(b) for b in reversed(bits or [0])) 

It is also faster than num_bin :

 >>> import timeit >>> t_bin = timeit.Timer('bin(0xf0)', 'from __main__ import bin') >>> print t_bin.timeit(number=100000) 4.19453350997 >>> t_num_bin = timeit.Timer('num_bin(0xf0)', 'from __main__ import num_bin') >>> print t_num_bin.timeit(number=100000) 4.70694716882 

Moreover, it really works correctly (for my definition of "correctness" :)):

 >>> bin(1) '1' >>> num_bin(1) '10000000'