Group binary bits together

Question

I have a list of numbers (here is an example with 4-bits numbers, but I want to do it with 16-bits integers) :

L = [0b1000,0b1100,0b1111,0b1001, 0b0000]

and I want to group all 1st bits together, then all 2nd bits together, then all 3rd bits together, etc., like this:

out = 0b11110011000010000110

This solution (proposed by @markcial) works :

print [[a[i] for a in [format(b,'04b') for b in L]] for i in range(4)]
#[['1', '1', '1', '1', '0'], ['0', '1', '1', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '1', '1', '0']]

but I would like to avoid string formatting to do these binary operations.

How to group bits together without using string formatting ?

Answer 1

Maybe this algorithm suits your needs, I will explain it with 4 bits digits and you can later expand it to be used with 16 bits.

L = [0b1000,0b1100,0b1111,0b1001, 0b0000]
bits = 4  # total bits
next_bit = bits*len(L)-1  # next position to be calculated
res = 0

for i in range(bits-1,-1,-1):  # iterate 3,2,1,0 (bits backwards)
    for x in L:                # iterate through every integer in L
        res = res | (((x&1<<i)>>i)<<next_bit)  # say what? o.O
        next_bit-=1            # set next_bit to the next position to be calculated

 >>> bin(res)
'0b11110011000010000110'

Basically, what it does is iterate through every bit position to be analize in each number, then iterate through each number to analyze that position, and once you know what position to analyze on what number, you perform this weird calculation: (((x&1<<i)>>i)<<total_bits-1).

The loop will accumulate on res the result of that calculation which I explain:

1. x&1<<i will test if the bit at position i is on
2. ((x&1<<i)>>i) shifting backwards i bits will make sure the result is 1 or 0
3. (((x&1<<i)>>i)<<next_bit) shifting forward next_bit will set the bit to 1 or 0 at position next_bit.

You need this next_bit integer to keep account of what's the next bit on the result you need to set. Since you have for example, 5 four bits digits, you know the result will have 5*4 bits.

I don't like much those two for loops. In C this is probably good but in Python they are not very efficient. I still thinking a way to remove them. I dare you to benchmark them with this simple oneliner:

>>>L = [0b1000,0b1100,0b1111,0b1001, 0b0000]
>>>int(''.join(['1' if x&1<<i else '0' for i in range(3,-1,-1) for x in L]),2)
995462

You'll be surprised about the performance.

Hope this helps!

Answer 2

Thanks to collaborative work with @PauloBu, here is what I was looking for (I admit my question was a bit unclear) : the output numbers are packed into bytes (8-bits) for easy writing into a file :

import struct
L = [0b1000,0b1100,0b1111,0b1001, 0b0000]
bits = 4
res = 0
processed_bits = 0
s = ''
for i in range(bits-1,-1,-1): 
    for x in L: 
        res = res | (((x&1<<i)>>i) << (7-processed_bits))  
        processed_bits += 1           
        if processed_bits == 8:
            s += struct.pack('B', res)
            res = 0
            processed_bits = 0

with open('blah.bin', 'wb') as f:
    f.write(s)