Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

The difference between logical shift right, arithmetic shift right, and rotate right

I've been reading the classic Hacker's delight and I am having trouble understanding the difference between logical shift right,arithmetic shift right, and rotate right. Please excuse if the doubt seems too simple.

Also why is there no arithmetic shift left?

like image 786
Chandrahas Aroori Avatar asked Jun 22 '17 09:06

Chandrahas Aroori


People also ask

What is the difference between arithmetic shift and logic shift micro operations?

Arithmetic shift preserve sign bit, whereas Logical shift can not preserve sign bit. Arithmetic shift perform multiplication and division operation, whereas Logical shift perform only multiplication operation. Arithmetic shift is used for signed interpretation, whereas Logical shift is used for unsigned interpretation.

What is meant by arithmetic right shift?

Logical right shifts are equivalent to division by a power of the radix (usually 2) only for positive or unsigned numbers. Arithmetic right shifts are equivalent to logical right shifts for positive signed numbers.

Is arithmetic and logical left shift same?

A Left Arithmetic Shift of one position moves each bit to the left by one. The vacant least significant bit (LSB) is filled with zero and the most significant bit (MSB) is discarded. It is identical to Left Logical Shift.

How is logical shift right different from logical shift left?

A Logic Shift simply moves a set of bits right or left. A left shift pushes in a zero into the least significant bit position. For an unsigned integer, this is equivalent to a multiplication by 2. A right shift pushes in a zero into the most significant bit position.


2 Answers

First remember that machine words are of fixed size. Say 4, and that your input is:

+---+---+---+---+ | a | b | c | d | +---+---+---+---+ 

Then pushing everything one position to the left gives:

+---+---+---+---+ | b | c | d | X | +---+---+---+---+ 

Question what to put as X?

  1. with a shift put 0
  2. with rotate put a

Now push everything one position to the right gives:

+---+---+---+---+ | X | a | b | c | +---+---+---+---+ 

Question what to put as X?

  1. with a logical shift put 0
  2. with an arithmetic shift put a
  3. with rotate put d

Roughly.

Logical shift correspond to (left-shift) multiplication by 2, (right-shift) integer division by 2.

Arithmetic shift is something related to 2's-complement representation of signed numbers. In this representation, the sign is the leftmost bit, then arithmetic shift preserves the sign (this is called sign extension).

Rotate has no ordinary mathematical meaning, and is almost an obsolete operation even in computers.

like image 125
Jean-Baptiste Yunès Avatar answered Oct 03 '22 07:10

Jean-Baptiste Yunès


The difference is pretty much explained in the right-most column.

  • Logical shift treats the number as a bunch of bits, and shifts in zeros. This is the >> operator in C.
  • Arithmetic shift treats the number as a signed integer (in 2s complement), and "retains" the topmost bit, shifting in zeros if the topmost bit was 0, and ones if it was one. C's right-shift operator has implementation-defined behavior if the number being shifted is negative.

    For example, the binary number 11100101 (-27 in decimal, assuming 2s complement), when right-shifted 3 bits using logical shift, becomes 00011100 (decimal 28). This is clearly confusing. Using an arithmetic shift, the sign bit would be kept, and the result would become 11111100 (decimal -4, which is about right for -27 / 8).

  • Rotation does neither, since topmost bits are replaced by lowermost bits. C does not have an operator to do rotation.

like image 42
unwind Avatar answered Oct 03 '22 08:10

unwind