python reverse a binary pattern within an integer

Question

Is there a fast possibility to reverse a binary number in python?

Example: I have the number 11 in binary 0000000000001011 with 16 Bits. Now I'm searching for a fast function f, which returns 1101000000000000 (decimal 53248). Lookup tables are no solutions since i want it to scale to 32Bit numbers. Thank you for your effort.

Edit:

Performances. I tested the code for all 2^16 pattern several times.

winner are the partially look up tables: 30ms
2nd int(format(num, '016b')[::-1], 2) from the comments: 56ms
3rd x = ((x & 0x00FF) << 8) | (x >> 8): 65ms
I did not expect my approach to be so horribly slow but it is. approx. 320ms. Small improvement by using + instead of | 300ms
bytes(str(num).encode('utf-8')) fought for the 2nd place but somehow the code did not provide valid answers. Most likely because I made a mistake by transforming them into an integer again.

thank you very much for your input. I was quite surprised.

H L · Accepted Answer · 2020-09-01 21:36:51Z

3

This might be faster using small 8-bit lookup table:

num = 11
# One time creation of 8bit lookup
rev = [int(format(b, '08b')[::-1], base=2) for b in range(256)]

# Run for each number to be flipped.
lower_rev = rev[num & 0xFF] << 8
upper_rev = rev[(num & 0xFF00) >> 8]
flipped = lower_rev + upper_rev

answered Sep 1, 2020 at 21:36

H L

562 bronze badges

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

1 Comment

Duda Over a year ago

thank you, I guess partly using luts is probably the fastest solution. I will run a test and post my results

Ethan · Accepted Answer · 2020-09-01 20:55:09Z

1

I think you can just use slicing to get what you are looking for:

b=bytes('0000000000001011'.encode('utf-8'))
>>> b
b'0000000000001011'
>>> b[::-1]
b'1101000000000000'

answered Sep 1, 2020 at 20:55

Ethan

1,3831 gold badge8 silver badges8 bronze badges

2 Comments

khelwood Over a year ago

Why would you encode to bytes instead of just reversing the string?

Ethan Over a year ago

@khelwood the original question didn’t show the type. I cast as bytes on the assumption (possibly incorrectly) that the data is in bytes. The slicing would work equally as well on a string

superb rain · Accepted Answer · 2020-09-01 21:27:34Z

1

There's this, but in Python it seems slower than Matthias' proposed int->str->int solution.

x = ((x & 0x5555) << 1) | ((x & 0xAAAA) >> 1)
x = ((x & 0x3333) << 2) | ((x & 0xCCCC) >> 2)
x = ((x & 0x0F0F) << 4) | ((x & 0xF0F0) >> 4)
x = ((x & 0x00FF) << 8) | (x >> 8)

answered Sep 1, 2020 at 21:27

superb rain

5,5612 gold badges15 silver badges25 bronze badges

Comments

Duda · Accepted Answer · 2020-09-02 09:43:18Z

1

My current approach is to access the bits via bit shifting and mask and to shift them in the mirror number until they reach their destination. Still I have the feeling that there is room for improvement.

num = 11
print(format(num, '016b'))

right = num
left = 0
for i in range(16):
  tmp = right & 1
  left = (left << 1 ) | tmp
  right = right >> 1


print(format(left, '016b'))

edited Sep 2, 2020 at 9:43

answered Sep 1, 2020 at 20:48

Duda

3,7465 gold badges20 silver badges37 bronze badges

4 Comments

Matthias Over a year ago

What about print(int(format(num, '016b')[::-1], 2)).

Jan Stránský Over a year ago

@Matthias IMO int->str->int does not satisfies the requirement for "fast function"..

superb rain Over a year ago

@JanStránský So you have something faster?

Matthias Over a year ago

@JanStránský This was the first idea I had (still waiting for other solutions to come up). If you want a really fast function then you could write a library in C. Still benchmarking would be needed to see which solution is the fastest.

Collectives™ on Stack Overflow

python reverse a binary pattern within an integer

4 Answers 4

1 Comment

2 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related