Efficient way to transpose the bit of an integer in python?

Question

Consider a 6 bits integer

x = a b c d e f

that should be transpose to three integers of 2 bits as follows

x1 = a d  
x2 = b e
x3 = c f

What is an efficient way to do this in python?

I currently goes as follows

bit_list = list( bin(x)[2:] ) # to chop of '0b'

# pad beginning if necessary, to make sure bit_list contains 6 bits
nb_of_bit_to_pad_on_the_left = 6 - len(bit_list)

for i in xrange(nb_of_bit_to_pad_on_the_left):
    bit_list.insert(0,'0')

# transposition
transpose = [ [], [], [] ]
for bit in xrange(0,  6, 2):
    for dimension in xrange(3):
        x = bit_list[bit + dimension]
        transpose[dimension].append(x)

for i in xrange(n):
    bit_in_string = ''.join(transpose[i])
    transpose[i] = int(bit_in_string, 2)

but this is slow when transposing a 5*1e6 bits integer, to one million of 5 bits integer.

Is there a better method?
Or some bitshit magic <</>> that will be speedier?

This question arised by trying to make a python implementation of Skilling Hilbert curve algorithm

Bakuriu · Accepted Answer · 2013-10-20T17:01:46.150

3

This should work:

mask = 0b100100

for i in range(2, -1, -1):
    tmp = x & mask
    print(((tmp >> 3 + i) << 1) + ((tmp & (1 << i)) >> i))
    mask >>= 1

The first mask extracts only a and d, then it is shifted to extract only b and e and then c and f.

In the print statement the numbers are either x00y00 or 0x00y0 or 00x00y. The (tmp >> 3 + i) transforms these numbers into x and then the << 1 obtains x0. The ((tmp & (1 << i)) >> i)) first transforms those numbers into y00/y0 or y and then right-shifts to obtain simply y. Summing the two parts you get the xy number you want.

edited Oct 20 '13 at 17:01

answered Oct 20 '13 at 16:50

Bakuriu

98,325
22
197
231

Great answer, thanks. Can you indicate how to efficiently generates the mask for other partitioning, like a 15 bits to three 5 bits. I only can do it with `mask=[]; mask.append ... ; int(mask,2)`. – Oct 20 '13 at 17:06
Ah, it's ok, for 15 to 5, I can do: `mask = 2**14 + 2**(14-5)`. Thanks – Oct 20 '13 at 17:12
I forgot one term: `mask = 2**14 + 2**(14-5) + 2**(14-2*5)` – Oct 20 '13 at 17:20

score 1 · Answer 2 · answered Oct 20 '13 at 17:13

1

Slices will work if your working with strings ( bin(x) ).

>>> 
>>> HInt = 'ABCDEFGHIJKLMNO'
>>> x = []
>>> for i in [0, 1, 2]:
    x.append(HInt[i::3])


>>> x[0]
'ADGJM'
>>> x[1]
'BEHKN'
>>> x[2]
'CFILO'
>>>

answered Oct 20 '13 at 17:13

wwii

23,232
7
37
77

Efficient way to transpose the bit of an integer in python?

2 Answers2

Linked