Hướng dẫn python circular bit shift

Question

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

Nội dung chính Show

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

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'

I'm a beginner coder and I'm trying to find cyclic shifts of strings. A cyclic shift of a string is obtained by moving characters from the beginning of the string to the end of the string. For example, the cyclic shifts of ABCDE are: ABCDE, BCDEA, CDEAB, DEABC, EABCD. The input will consist of exactly two lines containing only uppercase letters. The first line will be the text T, and the second line will be the string S.

Output yes if the text, T, contains a cyclic shift of the string, S. Otherwise, output no.

Sample Input:

ABCCDEABAA
ABCDE

Output for Sample Input:

yes

Tom Karzes

20.4k2 gold badges17 silver badges37 bronze badges

3

So basically you can append the string S to itself and lets call this string S2

s = 'ABCDE'
s2 = s + s    # s2 = 'ABCDEABCDE'

Since the length of the string S is 5, you will have to check whether s2[i:i+5] exists in T or not.

Code

t = 'ABCCDEABAA'
s = 'ABCDE'
s2 = s + s
n = len(s)

for i in range(n):
    flag = False
    if s2[i:i+n] in t:
        flag = True

    print(f"Checking for {s2[i:i+n]:s} in T = {flag}")

Output

Checking for ABCDE in T = False
Checking for BCDEA in T = False
Checking for CDEAB in T = True
Checking for DEABC in T = False
Checking for EABCD in T = False

Time complexity : O(len(s)) * O(string_comparison)

answered Mar 19 at 8:31

DollarAkshayDollarAkshay

2,0741 gold badge19 silver badges38 bronze badges

View Discussion

Improve Article

Save Article

Read

Discuss

View Discussion

Improve Article

Save Article

Given a string of size n, write functions to perform following operations on string.

Left (Or anticlockwise) rotate the given string by d elements (where d <= n).
Right (Or clockwise) rotate the given string by d elements (where d <= n).

Examples:

Input : s = "GeeksforGeeks"
        d = 2
Output : Left Rotation  : "eksforGeeksGe" 
         Right Rotation : "ksGeeksforGee"  


Input : s = "qwertyu" 
        d = 2
Output : Left rotation : "ertyuqw"
         Right rotation : "yuqwert"

Method 1: We have existing solution for this problem please refer Left Rotation and Right Rotation of a String link. We will solve this problem quickly in python using String Slicing. Approach is very simple,

Separate string in two parts first & second, for Left rotation Lfirst = str[0 : d] and Lsecond = str[d :]. For Right rotation Rfirst = str[0 : len(str)-d] and Rsecond = str[len(str)-d : ].
Now concatenate these two parts second + first accordingly.

Implementation:

Python3

def rotate(input,d):

Lfirst = input[0 : d]

Lsecond = input[d :]

Rfirst = input[0 : len(input)-d]

Rsecond = input[len(input)-d : ]

print ("Left Rotation : ", (Lsecond + Lfirst) )

print ("Right Rotation : ", (Rsecond + Rfirst))

if __name__ == "__main__":

input = 'GeeksforGeeks'

d=2

rotate(input,d)

Output:

Left Rotation  : eksforGeeksGe 
Right Rotation : ksGeeksforGee

Method 2: We use extended string to rotate the string. We will solve this problem quickly in python by slicing extended string. Approach is very simple,

Use extended string Extend_str, for Left rotation Lfirst = Extended_str[n : l1+n] . For Right rotation Rfirst = str[l1-n : l2-n].
Now print this string.

Implementation:

Python3

def rotate(str1,n):

temp = str1 + str1

l1 = len(str1)

l2 = len(temp)

Lfirst = temp[n : l1+n]

Lfirst = temp[l1-n : l2-n]

print ("Left Rotation : ", Lfirst)

print ("Right Rotation : ", Lfirst )

if __name__ == "__main__":

input = 'GeeksforGeeks'

d=2

rotate(input,d)

Output

Left Rotation :  ksGeeksforGee
Right Rotation :  ksGeeksforGee

programming python Circular shift Java C rotate right

Hướng dẫn python circular bit shift

Code

Output

Python3

Python3

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội