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-20 17:01:46Z

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, 2013 at 17:01

answered Oct 20, 2013 at 16:50

Bakuriu

103k23 gold badges208 silver badges236 bronze badges

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

3 Comments

user1030312 Over a year ago

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

user1030312 Over a year ago

Ah, it's ok, for 15 to 5, I can do: mask = 2**14 + 2**(14-5). Thanks

user1030312 Over a year ago

I forgot one term: mask = 2**14 + 2**(14-5) + 2**(14-2*5)

wwii · Accepted Answer · 2013-10-20 17:13:30Z

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, 2013 at 17:13

wwii

23.9k7 gold badges42 silver badges80 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related