Circular shift on the binary representation of an integer by `k` positions

Given two positive integers n and k, perform a circular shift on the binary representation of n by k positions.

The circular shift can be of two types:

Left circular shift (moving the final bit to the first position while shifting all other bits to the next position).
Right circular shift (moving the first bit to the last position while shifting all other bits to the previous position).

For example,

Input:

N = 127        (00000000000000000000000001111111)
shift = 3

Output:

Left Shift     00000000000000000000001111111000
Right Shift    11100000000000000000000000001111

Practice this problem

The idea is to perform a normal bitwise left or right shift by first isolating the sequence of k–bits from the right or left side, respectively. Finally, return the bitwise OR of the shifted number with isolated bits at their correct position.

For example, consider n = 127 which is 00000000000000000000000001111111.

Circular Right shift by 3:

1. Isolate the 3–bits from the right:

00000000000000000000000001111111

2. Right shift by 3

00000000000000000000000001111111
00000000000000000000000000001111

3. OR with isolated bits:

00000000000000000000000000001111
11100000000000000000000000000000
————————————————————————————————
11100000000000000000000000001111

Circular Left shift by 3:

1. Isolate the 3–bits from the left:

00000000000000000000000001111111

2. Left shift by 3:

00000000000000000000000001111111
00000000000000000000001111111000

3. OR with isolated bits:

00000000000000000000001111111000
00000000000000000000000000000000
————————————————————————————————
00000000000000000000001111111000

Following is the C++ and Java program that demonstrates it:

C++

#include <iostream>

#include <bitset>

using namespace std;

// A macro that defines integer size

#define SIZE_INT sizeof(int) * 8

// Function to perform left circular shift or right circular shift

// on integer `n` by `k` positions based on flag `isLeftShift`

int circularShift(unsigned n, int k, bool isLeftShift)

{

// left shift by `k`

if (isLeftShift) {

return (n << k) | (n >> (SIZE_INT - k));

}

// right shift by `k`

return (n >> k) | (n << (SIZE_INT - k));

}

int main()

{

unsigned n = 127;

int shift = 3;

cout << "No Shift " << bitset<32>(n) << endl;

cout << "Left Shift " << bitset<32>(circularShift(n, shift, true)) << endl;

cout << "Right Shift " << bitset<32>(circularShift(n, shift, false)) << endl;

return 0;

}

Download Run Code

Java

class Main

{

public static String toBinaryString(int n)

{

return String.format("%32s", Integer.toBinaryString(n))

.replaceAll(" ", "0");

}

// Function to perform left circular shift or right circular

// shift on integer `n` by `k` positions based on flag `isLeftShift`

public static int shift(int n, int k, boolean isLeftShift)

{

// left shift by `k`

if (isLeftShift) {

return (n << k) | (n >> (Integer.SIZE - k));

}

// right shift by `k`

return (n >> k) | (n << (Integer.SIZE - k));

}

public static void main(String[] args)

{

int n = 127;

int shift = 3;

System.out.println("No Shift " + toBinaryString(n));

System.out.println("Left Shift " + toBinaryString(shift(n, shift, true)));

System.out.println("Right Shift " + toBinaryString(shift(n, shift, false)));

}

Download Run Code

Output:

No Shift 00000000000000000000000001111111
Left Shift 00000000000000000000001111111000
Right Shift 11100000000000000000000000001111