The difference between logical shift right, arithmetic shift right, and rotate right
Solution 1
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?
- with a shift put 0
- with rotate put
a
Now push everything one position to the right gives:
+---+---+---+---+
| X | a | b | c |
+---+---+---+---+
Question what to put as X?
- with a logical shift put 0
- with an arithmetic shift put
a
- 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.
Solution 2
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 number11100101
(-27 in decimal, assuming 2s complement), when right-shifted 3 bits using logical shift, becomes00011100
(decimal 28). This is clearly confusing. Using an arithmetic shift, the sign bit would be kept, and the result would become11111100
(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.
Solution 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.
Related videos on Youtube
Chandrahas Aroori
Full Stack Dev @ Microsoft. Loves working with C, Python & Java. JS is kind of meh.
Updated on July 09, 2022Comments
-
Chandrahas Aroori almost 2 years
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.
-
Sourav Ghosh almost 7 yearsWhat this has to do with C?
-
Lundin almost 7 yearsWhat's wrong with the wikipedia articles? What is it that you don't understand about them?
-
Chandrahas Aroori almost 7 yearsI did not understand the difference between the arithmatic and logical shift.
-
-
Chandrahas Aroori almost 7 yearsCan you explain arithmatic shift a little more clearly. And example please?
-
phuclv almost 7 years@ChandrahasAroori there are tons of examples that you can find on google en.wikipedia.org/wiki/Bitwise_operation
-
endolith over 5 years"Shift" could be more specifically referred to as "logical shift", no?
-
Jed over 4 yearsLogical shift does not divide and multiply by 2. For example, -75 >>> 1 = 90. The arithmetic shift preserves the sign, thus multiplying and dividing by 2
-
Jean-Baptiste Yunès over 4 yearsI never said taht logical shift are for 2's complement numbers, only arithmetic shift.
-
Peter Cordes over 4 yearsUseful to note that arithmetic right shift rounds towards
-Infinity
while ordinary signed division (in C) truncated towards 0. So compilingx/2
for signed x requires some sign-bit trickery on top of an SAR instruction. -
KMC almost 4 years"11111100 (decimal ~4)" .. isn't that negative of 00000011 or -3 instead ?
-
Bbake Waikhom over 2 yearsThe definition of Logical shift and Arithmetic shift at the end is incorrect. The arithmetic shift is the one that's used to divide or multiply by 2, not the Logical shift. Please correct.