CODEWITHSUNDEEP
pythonoptimizationbit-manipulationbit-shift
Beef Wellington
Beef Wellington

Reputation: 1

Performing Arbitrarily Large Bit Rotations on an Integer

I am trying to perform very large bit rotations on non-negative 16-bit integers in Python, however it is very slow. I tried optimizing the process by shifting it by the modulo of 16, but it leaves a bunch of zeros at the end of it. Is there any way to fix this? Can we truncate the binary to a 16 bit window? Are there any other methods to improve performance? I can not use any external libraries.

An example of the operation is 23748 >> 8857328954.

Here is an example of some code I tried:

x = 35233
y = 738337234 % 16
x >> y

Upvotes: 0

Views: 51

Answers (1)

Dillon Davis
Dillon Davis

Reputation: 7750

The >> operator is not a circular shift- it will completely discard values shifted beyond the LSB, rather than wrapping around to the MSBs:

>>> bin(51)[2:].zfill(6)
'110011'
>>> bin(51 >> 3)[2:].zfill(6)
'000110'

Your idea of taking the second operand modulo the bit length of the first operand is on the right track, but you'll need to perform some extra operations to recover those discarded bits.

def cshift_right(num, dist):
     v1 = num >> (dist % 16)                  # this is your original logic
     v2 = (num << (16 - dist % 16)) & 0xFFFF  # shift left, and mask off higher bits
     return v1 | v2                           # combine the two results

Verifying that this works:

>>> bin(51)[2:].zfill(16)
'0000000000110011'
>>> bin(cshift_left(51, 3))[2:].zfill(16)
'0110000000000110'

Upvotes: 1

Related Questions