Python Convert a list of binary to string

Question

I have a list of 1 and 0 --> output = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0]

I would like to convert that list of ones and zeroes to a string, where each 8 bits in "litlle-endian" represent one letter in "latin1"

So far I have this code (below) which works fine, but I think its quite slow and seem to slow down my script...

for i in range(0,len(output),8):
        x=output[i:i+8]
        l="".join([str(j) for j in x[::-1]])
        out_str += chr(int(("0b"+l),base=2))

Do you have any faster ideas?

What are you using this routine for? Are you repeatedly doing this on lists of multiple thousands of different values? I had to run your sample 100,000 times (!) to get more than sub-second timings. If the output is text, I'd have decoded 200,000 characters – about a thousand pages in a book. — Jongware
– Jongware, Commented Mar 8, 2020 at 23:51

Alain T. · Accepted Answer · 2020-03-09 23:56:55Z

3

Here's a faster solution using a dictionary of tuples for the 256 possible characters:

bits = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0]

chars = { tuple(map(int,f"{n:08b}"[::-1])):chr(n) for n in range(0,256) }

def toChars(bits):
    return "".join(chars[tuple(bits[i:i+8])] for i in range(0,len(bits),8) )

roughly 3x faster than original solution

[EDIT] and an even faster one using bytes and zip:

chars = { tuple(map(int,f"{n:08b}")):n for n in range(256) }
def toChars(bits):
    return bytes(chars[b] for b in zip(*(bits[7-i::8] for i in range(8)))).decode()

about 2x faster than the previous one (on long lists)

[EDIT2] a bit of explanations for this last one ...

b in the list comprehension will be a tuple of 8 bits
chars[b] will return an integer corresponding to the 8 bits
bytes(...).decode() converts the list of integers to a string based on the chr(n) of each value
zip(*(... 8 bit iterators...)) unpacks the 8 striding ranges of bits running in parallel, each from a different starting point

The strategy with the unpacked zip is to go through the bits in steps of 8. For example, if we were going through 8 parallel ranges, we would get this:

 bits[7::8] -> [ 0, 0, ... ]  zip returns: (0,1,0,0,0,1,1)
 bits[6::8] -> [ 1, 1, ... ]               (0,1,1,0,1,1,1)
 bits[5::8] -> [ 0, 1, ... ]               ...
 bits[4::8] -> [ 0, 0, ... ]
 bits[3::8] -> [ 0, 1, ... ]
 bits[2::8] -> [ 0, 1, ... ]
 bits[1::8] -> [ 1, 1, ... ]
 bits[0::8] -> [ 1, 1, ... ]

The zip function will take one column of this per iteration and return it as a tuple of bits.

edited Mar 9, 2020 at 23:56

answered Mar 9, 2020 at 1:34

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

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

1 Comment

MrZH6 Over a year ago

Great solution! Took me some while to get a grasp of it. I edited my answer with a noob version of your code :-)

Alex Reynolds · Accepted Answer · 2020-03-08 23:18:02Z

1

#!/usr/bin/python                                                                                                                                                                                                                                                                                                                                                         

bits = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0]
result = []

c = 0
for i,v in enumerate(bits):
    i = i % 8
    c = c | v << i
    if i == 7:
        result.append(chr(c))
        c = 0

print(''.join(result))

Testing:

$ python ./test.py
Co

answered Mar 8, 2020 at 23:18

Alex Reynolds

97.3k59 gold badges251 silver badges356 bronze badges

Comments

Jongware · Accepted Answer · 2020-03-08 23:40:22Z

1

Using sum and enumerate should be faster, as they are built-ins. Let's time yours and mine, on the same machine.

Run 100,000 times in a loop and tested with time python3 tmp.py. (user values. For both the amount of sys time hovered around 0m0.012s, so it only had a percentual influence on the results.)

Yours: 0m1.624s
Mine is 50% faster: 0m1.063s, with this

output = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0]

for item in [output[i:i + 8] for i in range(0, len(output), 8)]:
    out_str += chr(sum(x<<i for i,x in enumerate(item)))

answered Mar 8, 2020 at 23:40

Jongware

22.6k8 gold badges56 silver badges104 bronze badges

1 Comment

Jongware Over a year ago

... since it's only 8 values, [x<<i] can be 'cached' as [1,2,4,8,16,32,64,128] and then cross-multiplied or sth. But it's late over here.

MrZH6 · Accepted Answer · 2020-03-10 21:06:38Z

I did some measuments of the execution time for all valid solutions. See the results below in the code. Codes are sorted from slowest to fastest. Fatest being the one from Alain T.. I've tested the codes on a quite large list resulting in a string of 200000 characters.

Even for such a large list the execution time is still pretty fast also for my original solution. There has to be an issue somewhere else in my program... :-)

Thank you all for your codes!

import time
start_time = time.time()
bits = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0] * 100000
    ### tested code ###
print("Execution time: ", time.time() - start_time, "seconds")


### former solution --> 0.59 seconds
out_str = ""
for i in range(0,len(bits),8):
    x=bits[i:i+8]
    l="".join([str(j) for j in x[::-1]])
    out_str += chr(int(("0b"+l),base=2))


### enumerate and result.append --> 0.48 seconds
result = []
c = 0
for i,v in enumerate(bits):
    i = i % 8
    c = c | v << i
    if i == 7:
        result.append(chr(c))
        c = 0
out_str = ''.join(result)


### sum and enumerate --> 0.45 seconds
out_str = ""
for item in [bits[i:i + 8] for i in range(0, len(bits), 8)]:
    out_str += chr(sum(x<<i for i,x in enumerate(item)))


### map and chars dictionary --> 0.10 seconds
chars = { tuple(map(int,f"{n:08b}"[::-1])):chr(n) for n in range(0,256) }
def toChars(bits):
    return "".join(chars[tuple(bits[i:i+8])] for i in range(0,len(bits),8) )


### bytes and zip --> 0.06 seconds
chars = { tuple(map(int,f"{n:08b}")):n for n in range(256) }
def toChars(bits):
    return bytes(chars[b] for b in zip(*(bits[7-i::8] for i in range(8)))).decode()

EDIT:

I wrote the best (fastest) solution in a more understandable form (not using list comprehensions) so I could step through the code because it took me some while to understand how it works (solution by Alain T.):

bits = [1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0] * 10
chars = {tuple(map(int,f"{n:08b}")):n for n in range(256)}
temp = []
out = []
for i in range(8):
    temp.append(bits[7-i::8])
unzipped = zip(*temp)
for b in unzipped:
    out.append(bytes([chars[b]]).decode())
print("".join(out))

Błotosmętek · Accepted Answer · 2020-03-08 21:22:49Z

-1

Check whether this is faster:

tmp_list = []
for i in range(0,len(output),8):
    byte_value = 0
    for digit in output[i:i+8:-1]:
        byte_value = (byte_value<<1) + digit
    tmp_list.append(chr(byte_value))
out_str = ''.join(tmp_list)

answered Mar 8, 2020 at 21:22

Błotosmętek

13k23 silver badges30 bronze badges

1 Comment

MrZH6 Over a year ago

Shouldn't the second for cycle be: for digit in output[i+8:i:-1]? But anyway it doesn't seem to work. The result should be "Co" for this one.

Collectives™ on Stack Overflow

Python Convert a list of binary to string

5 Answers 5

1 Comment

Comments

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related