Skip to content

Arithmetic and Logical Right Shifts

The logical right shift means shifting the bits to the right, and MSB(most significant bit) becomes 0. The arithmetic right shift means shifting the bits to the right, and MSB is the same as in the original number.

Gopi Gorantala
Gopi Gorantala
3 min read

Introduction

The logical right shift means shifting the bits to the right, and MSB(most significant bit) becomes 0. The arithmetic right shift means shifting the bits to the right, and MSB is the same as in the original number.

Logical right shift (>>>)

The logical right-shift operator is written as >>>.

Integers are stored in memory as a series of bits. For example, the number 12 stored as a 32-bit int would be:

12 = 00000000 00000000 00000000 00001100

When we shift it one position (12 >>> 1), the answer is 6.

12 >>> 1 = 12/21 = 12/2 = 6

The binary representation of the number 6 is as follows.

(12 >>> 1) = 00000000 00000000 00000000 00000110

Let’s see how to represent this in a mathematical formula.

Formula

a >>> b = a/2b

Arithmetic right shift (>>)

Right shift

The right shift operator is written as >>.

Integers are stored in memory as a series of bits. For example, the number 6 stored as a 32-bit int would be:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the right one position (6 >> 1) would result in the number 3:

 6 >> 1 = 00000000 00000000 00000000 00000011

As you can see, the digits have shifted to the right by one position, and the last digit on the left is filled with a zero. You might also note that shifting right is equivalent to dividing by powers of 2.

So,

6 >> 1 => 6/21 = 6/2 = 3

6 >> 3 => 6/23 = 6/8 = 0

A good optimization compiler will replace division with shifts when possible.

1011 >> 1  →  1101
1011 >> 3  →  1111

0011 >> 1  →  0001
0011 >> 2  →  0000

The first two numbers had a 1 as the most significant bit, so more 1's were inserted during the shift. The last two numbers had a 0 as the most significant bit, so the shift inserted more 0's.

If a number is encoded using two’s complement, then an arithmetic right shift preserves the number’s sign, while a logical right shift makes the number positive.

// Arithmetic shift
1011 >> 1  →  1101    
	1011 is -5    
	1101 is -3

So, in simple terms, >> (right shift) takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift.

Let’s see how to represent this in a mathematical formula.

Formula

x >> y = x/2y

For example, if we interpret this bit pattern as a negative number.

10000000 00000000 00000000 01100000

we have the number -2,147,483,552. Shifting this to the right 4 positions with the arithmetic shift (-2,147,483,552 >> 4) would give us:

11111000 00000000 00000000 00000110

or the number -134,217,722

So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift rather than the logical right shift. Moreover, once again, we see that we are performing division by powers of 2.

a >> b = a/2b

Solution

Java

class RightShift {
   private static int helper(int number, int i) {
        return number >> i;// divides `number` with 2^i times.
    }

    public static void main(String[] args) {
        int number = 100;

        System.out.println(number + " shifted 1 position right, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions right, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions right, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions right, yields to " + helper(number, 4));
    }
}

Python

def helper(number,i):
    return number >> i

number=100
print(number , "shifted 1 position left,yields to ",helper(number,1))
print(number , "shifted 2 position left,yields to ",helper(number,2))
print(number , "shifted 3 position left,yields to ",helper(number,3))
print(number , "shifted 4 position left,yields to ",helper(number,4))

JavaScript

const RightShift = (number, i) => number >> i;

let number = 100;

console.log (number + " shifted 1 position right, yields to " + RightShift (number, 1));
console.log (number + " shifted 2 positions right, yields to " + RightShift (number, 2));
console.log (number + " shifted 3 positions right, yields to " + RightShift (number, 3));
console.log (number + " shifted 4 positions right, yields to " + RightShift (number, 4));

C++

#include <iostream>

using namespace std;

int helper(int number, int i) {
    return number >> i;
}

int main() {
    int number = 100;
    cout << number << " shifted 1 position left , yields to " << helper(number, 1) << endl;
    cout << number << " shifted 2 position left , yields to " << helper(number, 2) << endl;
    cout << number << " shifted 3 position left , yields to " << helper(number, 3) << endl;
    cout << number << " shifted 4 position left , yields to " << helper(number, 4) << endl;
    return 0;
}

TypeScript

export const RightShift = (n: number, i: number): number => n >> i;

let n: number = 100;

console.log(n + " shifted 1 position right, yields to " + RightShift(n, 1));
console.log(n + " shifted 2 positions right, yields to " + RightShift(n, 2));
console.log(n + " shifted 3 positions right, yields to " + RightShift(n, 3));
console.log(n + " shifted 4 positions right, yields to " + RightShift(n, 4));

So, we see that shifting to the right is equivalent to division by powers of 2.

Bit ManipulationData Structures and Algorithms

Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Comments


Related Posts

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Leetcode 217: Contains Duplicate
Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Leetcode 121: Best Time To Buy and Sell Stock
Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things