Circular shift of a bit in python (equivalent of Fortran's ISHFTC)

Question

I want to achieve the equivalent of the ISHFTC function in Fortran using python. What is the best way to do this?

For example,

x = '0100110'
s = int(x, 2)
s_shifted = ISHFTC(s,1,7) #shifts to left by 1
#binary representation of s_shifted should be 1001100

My attempt based on Circular shift in c

def ISHFTC(n, d,N):  
    return (n << d)|(n >> (N - d))

However, this does not do what I want. Example,

ISHFTC(57,1,6) #57 is '111001'

gives 115 which is '1110011' whereas I want '110011'

Does this answer your question? [Circularly shifting (or rotating) the digits the digits of a number in Python](https://stackoverflow.com/questions/52555368/circularly-shifting-or-rotating-the-digits-the-digits-of-a-number-in-python) — Mario Ishac, Sep 05 '20 at 23:08
It's not *exactly* a duplicate but very close. You would need to perform the `rotr` in the link on `x`, not `s`. — Mario Ishac, Sep 05 '20 at 23:09
To be clear, the `7` in the function call here indicates the number of bits to interpret the number as using? — Karl Knechtel, Sep 05 '20 at 23:14
@MarioIshac I am dealing with binary numbers, so I thought there should be a more efficient solution without first transforming the integer representation to a string, then performing the shift, then transforming back to an int. — user1830663, Sep 05 '20 at 23:15
@KarlKnechtel Yes, here is a documentation I found https://gcc.gnu.org/onlinedocs/gcc-4.4.7/gfortran/ISHFTC.html — user1830663, Sep 05 '20 at 23:15
The point of the link is that the OP is already doing what you want (or at least close to it), while having wanted something else. :) Rather: are you familiar with the `>>` and `<<` operators? — Karl Knechtel, Sep 05 '20 at 23:16
@user1830663 No you're right there definitely is a more efficient way, and you may be able to convert something like https://stackoverflow.com/questions/13289397/circular-shift-in-c to Python. But at this point you'd want to deal with `numpy` ints rather than Python ints. — Mario Ishac, Sep 05 '20 at 23:18
@KarlKnechtel the << or >> do not effectuate a circular shift I think. Take 4 ('100'). 4<<1 =8 ('1000'). Instead of '001' which is what I want. — user1830663, Sep 05 '20 at 23:19
Correct. But perhaps you can think of a way to determine what bits will drop off the right-hand side when you `>>`, for example, and then to put them back on the left. — Karl Knechtel, Sep 05 '20 at 23:20
@MarioIshac I tried to adapt the c code, but it doesnt do exactly what I want. — user1830663, Sep 06 '20 at 17:49
Well - can you come up with a rule that tells you how far over to the left it should go? Can you come up with a technique that tells you what the data is that needs to be put there? — Karl Knechtel, Sep 07 '20 at 00:40

mkrieger1 · Accepted Answer · 2020-09-06T18:32:00.243

Your attempted solution does not work because Python has unlimited size integers.

It works in C (for specific values of N, depending on the type used, typically something like 8 or 32), because the bits that are shifted out to the left are automatically truncated.

You need to do this explicitly in Python to get the same behaviour. Truncating a value to the lowest N bits can be done be using % (1 << N) (the remainder of dividing by 2^N).

Example: ISHFTC(57, 1, 6)

We want to keep the 6 bits inside |......| and truncate all bits to the left. The bits to the right are truncated automatically, because the these are already the 6 least significant bits.

n                  |111001|
a = n << d        1|110010|
m = (1 << N)      1|000000|
b = a % m         0|110010|

c = n >> (N - d)   |000001|(11001)

result = b | c     |110011|

Resulting code:

def ISHFTC(n, d, N):  
    return ((n << d) % (1 << N)) | (n >> (N - d))
          #  ^^^^^^ a
          #             ^^^^^^ m
          #  ^^^^^^^^^^^^^^^^^ b
          #                         ^^^^^^^^^^^^ c

>>> ISHFTC(57, 1, 6)
51
>>> bin(_)
'0b110011'

Circular shift of a bit in python (equivalent of Fortran's ISHFTC)

1 Answers1