Base-2 (Binary) Representation Using Python

Building on How Do You Express Binary Literals in Python, I was thinking about sensible, intuitive ways to do that Programming 101 chestnut of displaying integers in base-2 form. This is the best I came up with, but I'd like to replace it with a better algorithm, or at least one that should have screaming-fast 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)])


Asked by: Ted420 | Posted: 06-10-2021






Answer 1

For best efficiency, you generally want to process more than a single 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 of x's lower 8 bits. This can be used to build a lookup table, allowing your converter to process 8 bits at a time (or more if you want to devote the memory to it).

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

Then you can use this in your real function, stripping off leading zeroes when returning it. I've also added handling for signed numbers, as without it you will get an infinite loop (Negative integers conceptually have an infinite number of set sign bits.)

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 to handle signed integers.
[Edit2] Here are some timing figures of the various solutions. bin is the function above, constantin_bin is from Constantin's answer and num_bin is the original version. Out of curiosity, I also tried a 16 bit lookup table variant of the above (bin16 below), and tried out Python3's builtin bin() function. All timings were for 100000 runs using an 01010101 bit pattern.

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's bin      0.079    0.045    0.062    0.069    0.212    0.201 

As you can see, when processing long values using large chunks really pays off, but nothing beats the low-level C code of python3's builtin (which bizarrely seems consistently faster at 256 bits than 128!). Using a 16 bit lookup table improves things, but probably isn't worth it unless you really need it, as it uses up a large chunk of memory, and can introduce a small but noticalbe startup delay to precompute the table.

Answered by: Victoria995 | Posted: 07-11-2021



Answer 2

Not screaming-fast, but straightforward:

>>> 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

Even more, it actually works correctly (for my definition of "correctness" :)):

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

Answered by: Lenny936 | Posted: 07-11-2021



Similar questions

module to create python object representation from xml


python - Printed representation of list

I want to format a list into a string in this way: [1,2,3] =&gt; '1 2 3'. How to do this? Is there any customizable formatter in Python as Common Lisp format?


how to use list of python objects whose representation is unicode

I have a object which contains unicode data and I want to use that in its representaion e.g. # -*- coding: utf-8 -*- class A(object): def __unicode__(self): return u"©au" def __repr__(self): return unicode(self).encode("utf-8") __str__ = __repr__ a = A() s1 = u"%s"%a # works #s2 = u"%s"%[a] # gives unicode decode error #s3 = u"%s"%unicode([a]) # gives unicode decode erro...


python - subclassing int to attain a Hex representation

Basically I want to have access to all standard python int operators, eg __and__ and __xor__ etc, specifically whenever the result is finally printed I want it represented in Hex format. (Kind of like putting my calculator into Hex mode) class Hex(int): def __repr__(self): return "0x%x"%self __str__=__repr__ # this certainly helps with printing if __name__=="__main__": ...


printing bit representation of numbers in python

I want to print the bit representation of numbers onto console, so that I can see all operations that are being done on bits itself. How can I possibly do it in python?


Visual representation of nodes in Python

I have data that I want to represent visually. The actual data is a tree made up of nodes. Each node has a bunch of data associated with it, but as far as this question goes, I just want a way to represent a tree visually using Python. Any ideas? The different solutions that popped in my head were to use a GUI library like WxPython or PyQT, or maybe even a PDF generator like ReportLab. I'm hoping there's a library ...


python - What class to use for money representation?

What class should I use for representation of money to avoid most rounding errors? Should I use Decimal, or a simple built-in number? Is there any existing Money class with support for currency conversion that I could use? Any pitfalls that I should avoid?


python - Generate a string representation of a one-hot encoding

In Python, I need to generate a dict that maps a letter to a pre-defined "one-hot" representation of that letter. By way of illustration, the dict should look like this: { 'A': '1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', 'B': '0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', # ... }


python - How can I view a text representation of an lxml element?

If I'm parsing an XML document using lxml, is it possible to view a text representation of an element? I tried to do : print repr(node) but this outputs &lt;Element obj at b743c0&gt; What can I use to see the node like it exists in the XML file? Is there some to_xml method or something?


introspection - How do I get the string representation of a variable in python?

I have a variable x in python. How can i find the string 'x' from the variable. Here is my attempt: def var(v,c): for key in c.keys(): if c[key] == v: return key def f(): x = '321' print 'Local var %s = %s'%(var(x,locals()),x) x = '123' print 'Global var %s = %s'%(var(x,locals()),x) f() The results are: Global var x = 123 Local var x = 321 ...






Still can't find your answer? Check out these communities...



PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python



top