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

Question

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.

---

Bounty:

Explain why arithmetic bit shifts as defined retain the semantics of approximate division/multiplication by $2^k$.

Answer 1

Logical Shift: Logical Shift means move everything to the right , filling empty spots with zeros.

Arithmetic Shift Right: Arithmetic Shift Right means Move Everything to the right ,filling empty spots with the sign bit.

Rotate Right : Rotate Right means move everything to the right , wrapping around bits that fall off to the left side.

Answer 2

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.

--EDIT---------------------

A note on arithmetic shift and 2-complement numbers.

For the sake of simplicity, suppose we work on binary representation of length 6.

For a digit a we denote its 2-complement by A and the converse (~a = A and ~A=a).

Any integer 0≤n<32 has the base 2 representation 0abcde, and its negative counterpart has the representation 1ABCDE + 1. Note that -0 has the same representation as 0.

We want x+-x=0, as 0abcde+1ABCDE = 111111, and 111111+1 = 000000 (fixed length representation we can omit the carry that overflows) we then know that -x is obtained by ~x+1.

Now what is the binary representation of -n/2?

The binary representation of n/2 is 00abcd, and its negative counterpart has the representation 11ABCD + 1, then to divide a 2's-complement binary number by 2 we just have to shift bits to the right and duplicate the original left bit on the same position.

Answer 3

Logical right shift means shifting the bits to the right and MSB(most significant bit) becomes 0.

Example: Logical right shift of number 1 0 1 1 0 1 0 1 is 0 1 0 1 1 0 1 0.

Arithmetic right shift means shifting the bits to the right and MSB(most significant bit) is same as in the original number.

Example: Arithmetic right shift of number 1 0 1 1 0 1 0 1 is 1 1 0 1 1 0 1 0.

Answer 4

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.