Bits list to integer in Python

Question

I have such list in Python: [1,0,0,0,0,0,0,0]. Can I convert it to integer like as I've typed 0b10000000 (i.e. convert to 128)? I need also to convert sequences like [1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0] to integers (here it will return 0b1100000010000000, i.e. 259). Length of list is always a multiple of 8, if it is necessary.

This might help you: stackoverflow.com/questions/2576712/… — Markus Unterwaditzer
– Markus Unterwaditzer, Commented Sep 17, 2012 at 14:26
Where are these lists coming from? Are they originally character input? — Steven Rumbalski
– Steven Rumbalski, Commented Sep 17, 2012 at 14:32
They are calculated from integers. If you want I can post code here. — ghostmansd
– ghostmansd, Commented Sep 17, 2012 at 14:35
@ghostmansd: I just wanted to make sure they weren't originally characters. That would have changed which answer was fastest. — Steven Rumbalski
– Steven Rumbalski, Commented Sep 17, 2012 at 14:40
@ghostmansd: What is the average length of your bitlist? At 64 bits the string version performs the best (on my computer). — Steven Rumbalski
– Steven Rumbalski, Commented Sep 17, 2012 at 15:11

Martijn Pieters · Accepted Answer · 2012-09-17 14:46:30Z

63

You can use bitshifting:

out = 0
for bit in bitlist:
    out = (out << 1) | bit

This easily beats the "int cast" method proposed by A. R. S., or the modified cast with lookup proposed by Steven Rumbalski:

>>> def intcaststr(bitlist):
...     return int("".join(str(i) for i in bitlist), 2)
... 
>>> def intcastlookup(bitlist):
...     return int(''.join('01'[i] for i in bitlist), 2)
... 
>>> def shifting(bitlist):
...     out = 0
...     for bit in bitlist:
...         out = (out << 1) | bit
...     return out
... 
>>> timeit.timeit('convert([1,0,0,0,0,0,0,0])', 'from __main__ import intcaststr as convert', number=100000)
0.5659139156341553
>>> timeit.timeit('convert([1,0,0,0,0,0,0,0])', 'from __main__ import intcastlookup as convert', number=100000)
0.4642159938812256
>>> timeit.timeit('convert([1,0,0,0,0,0,0,0])', 'from __main__ import shifting as convert', number=100000)
0.1406559944152832

edited Sep 17, 2012 at 14:46

answered Sep 17, 2012 at 14:25

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

ghostmansd Over a year ago

BTW, could you suggest the way to convert integer from 0b10000000 to 0b000001 without having to create list of bits?

Martijn Pieters Over a year ago

@ghostmansd: Use .format() string formatting: '0b{0:08b}'.format(integer) will format an integer to a 0-padded 8-character string with leading 0b.

arshajii Over a year ago

Yea that "int cast" method is what immediately sprung to my mind (seemed like a nice clean solution if you aren't too concerned with efficiency). But yes, this is clearly faster.

Steven Rumbalski Over a year ago

Here's a much faster string version: int(''.join('01'[i] for i in bitlist), 2). Still not as fast as bitshifting.

Martijn Pieters Over a year ago

@StevenRumbalski: Added it in the list of timings.

|

Fredrik Pihl · Accepted Answer · 2012-09-17 14:33:45Z

15

...or using the bitstring module

>>> from bitstring import BitArray
>>> bitlist=[1,0,0,0,0,0,0,0]
>>> b = BitArray(bitlist)
>>> b.uint
128

answered Sep 17, 2012 at 14:33

Fredrik Pihl

45.9k7 gold badges89 silver badges133 bronze badges

2 Comments

ghostmansd Over a year ago

I could use bitstring or bitarray modules before, but this time I can't. I need a solution which doesn't require additional packages. Thanks, however!

Fredrik Pihl Over a year ago

you didn't state that in the question, so I thought I'd add a bitstring-solution as an alternative to Martijns excellent answer :-)

Akavall · Accepted Answer · 2012-09-17 21:18:24Z

9

I came across a method that slightly outperforms Martijn Pieters solution, though his solution is prettier of course. I am actually a bit surprised by the results, but anyway...

import timeit

bit_list = [1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0]

def mult_and_add(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 + bit
    return output

def shifting(bitlist):
     out = 0
     for bit in bitlist:
         out = (out << 1) | bit
     return out

n = 1000000

t1 = timeit.timeit('convert(bit_list)', 'from __main__ import mult_and_add as convert, bit_list', number=n)
print "mult and add method time is : {} ".format(t1)
t2 = timeit.timeit('convert(bit_list)', 'from __main__ import shifting as convert, bit_list', number=n)
print "shifting method time is : {} ".format(t2)

Result:

mult and add method time is : 1.69138722958 
shifting method time is : 1.94066818592

answered Sep 17, 2012 at 21:18

Akavall

86.8k58 gold badges214 silver badges261 bronze badges

3 Comments

Zut Over a year ago

Slightly surprising result, yes. I'd guess that multiplication by two is exactly the same as shifting by one, but it could be due to that an OR operation is slower than a XOR operation. Addition can be simplified to XOR in your case since you won't have a carry, because of the bit shift.

Gregory Morse Over a year ago

It would be very interesting to know why this could possibly be. Obviously at the processor hardware level, the shifting pattern is certainly correct and well known for decades. However possible special code optimizations which are not apply to shifting, and are to multiplication and addition, which allow the processors pre-execution and branching prediction to work better, or it unrolls the loop or does something. There is an explanation and in part it means python's bitwise operation support of or and shifting is not very good.

Gregory Morse Over a year ago

Oh so by the way in Python 3.7.7, this is still true...

Python 3.7.7 (default, Mar 23 2020, 23:19:08) [MSC v.1916 64 bit (AMD64)] IPython 7.13.0 -- An enhanced Interactive Python.  %timeit mult_and_add(bit_list) 957 ns ± 3.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)  %timeit shifting(bit_list) 1.33 µs ± 11.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

arshajii · Accepted Answer · 2012-09-17 14:48:03Z

7

Try this one-liner:

int("".join(str(i) for i in my_list), 2)

If you're concerned with speed/efficiency, take a look at Martijn Pieters' solution.

edited Sep 17, 2012 at 14:48

answered Sep 17, 2012 at 14:25

arshajii

130k26 gold badges246 silver badges293 bronze badges

2 Comments

Steven Rumbalski Over a year ago

Here's a much faster string version: int(''.join('01'[i] for i in bitlist), 2). Still not as fast as bitshifting.

Steven Rumbalski Over a year ago

@ghostmansd. At 64 bits the string version starts to perform faster (on my computer).

Weidong He · Accepted Answer · 2019-04-18 19:36:45Z

6

how about this:

out = sum([b<<i for i, b in enumerate(my_list)])

or in reverse order:

out = sum([b<<i for i, b in enumerate(my_list[::-1])])

answered Apr 18, 2019 at 19:36

Weidong He

611 silver badge1 bronze badge

Comments

Jaakko · Accepted Answer · 2023-01-14 21:17:26Z

Fastest one-liner:

def reduced_plus(bitlist):
    return functools.reduce(lambda acc, val: acc * 2 + val, bitlist)

Benchmarking:

import timeit
import functools

def shifting_plus(bitlist):
    out = 0
    for bit in bitlist:
        out = out * 2 + bit
    return out

def shifting(bitlist):
    out = 0
    for bit in bitlist:
        out = (out << 1) | bit
    return out

def reduced_plus(bitlist):
    return functools.reduce(lambda acc, val: acc * 2 + val, bitlist)

def reduced(bitlist):
    return functools.reduce(lambda acc, val: acc << 1 | val, bitlist)

def summed(bitlist):
    return sum([b<<i for i, b in enumerate(bitlist)])

def intcastlookup(bitlist):
    return int(''.join('01'[i] for i in bitlist), 2)

cycles = 1_000_000
for fname in ["shifting_plus", "shifting", "reduced_plus", "reduced", "summed", "intcastlookup"]:
    result = timeit.timeit('convert([1,0,0,0,0,0,0,0])', f'from __main__ import {fname} as convert')
    print(f"{result:.3f} s - {fname}")

results:

0.465 s - shifting_plus
0.779 s - shifting
0.807 s - reduced_plus
0.841 s - summed
0.884 s - intcastlookup
1.024 s - reduced

ady · Accepted Answer · 2021-11-14 16:02:13Z

The simplest method suggested by @Akavall is the fastest one. The additional timing below for mult_add_xor shows that the bit operations are slower in python since simple addition "+ bit" is faster than xor "| bit" and the multiplication by 2 is faster than the bit shift "<< 1".

import timeit

bit_list = [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]


def mult_and_add(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 + bit
    return output


def mult_and_xor(bit_list):
    output = 0
    for bit in bit_list:
        output = output * 2 | bit
    return output


def shifting(bitlist):
    out = 0
    for bit in bitlist:
        out = (out << 1) | bit
    return out


n = 1000000

a1 = mult_and_add(bit_list)
a2 = mult_and_xor(bit_list)
a3 = shifting(bit_list)

print('a1: ', a1, ' a2: ', a2, ' a3: ', a3)
assert a1 == a2 == a3

t = timeit.timeit('convert(bit_list)',
                  'from __main__ import mult_and_add as convert, bit_list',
                  number=n)
print("mult and add method time is : {} ".format(t))
t = timeit.timeit('convert(bit_list)',
                  'from __main__ import mult_and_xor as convert, bit_list',
                  number=n)
print("mult and xor method time is : {} ".format(t))
t = timeit.timeit('convert(bit_list)',
                  'from __main__ import shifting as convert, bit_list',
                  number=n)
print("shifting method time is : {} ".format(t))

Output:

a1:  49280  a2:  49280  a3:  49280
mult and add method time is : 0.9469406669959426 
mult and xor method time is : 1.0905388034880161 
shifting method time is : 1.2844801126047969

Collectives™ on Stack Overflow

Bits list to integer in Python

7 Answers 7

13 Comments

2 Comments

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

13 Comments

2 Comments

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related