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$.

Portia

TLDR; Operations are on signed ints or unsigned ints. 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. Logical shift bits (not floating point fyi) just blindly moves things to the left or right. Rotates are never done in practice so forget it. – Vela

I personally feel the current answers have little use without understanding why retaining the 1s k times actually does the intended operation of dividing/multiplying the number by 2^k. – Vela

@CharlieParker Why do you edit a new question into an old question and bounty it instead of just asking a new question? Honest question, you probably know the site better than I do. – Durant

Answer 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?

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.

Shipman

"Shift" could be more specifically referred to as "logical shift", no? – Callender

Logical 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 – Chancroid

I never said taht logical shift are for 2's complement numbers, only arithmetic shift. – Flamsteed

Useful to note that arithmetic right shift rounds towards -Infinity while ordinary signed division (in C) truncated towards 0. So compiling x/2 for signed x requires some sign-bit trickery on top of an SAR instruction. – Methylnaphthalene

The 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. – Golly

@Chancroid For a logical shift, the signed representation of the number has no useful meaning. It's possible to write it just like you did where -75 changes to 90, but is that useful? Not really. When describing a logical shift as multiplication or integer division, the whole point is to treat all bits like unsigned integer bits. In that view, then multiplying and dividing by 2 is perfectly reasonable. – Watch

what about an arithmetic left shift? what does that mean mathematically? What I interpret if I understood your explanation, the most significant bit is always preserved, otherwise the meaning number completely changes randomly. So a single left arithmetic shift I'd assume "adds twice as much" to the number. i.e., we shift the bits in the two's complement that add and keep the sign bit as is. Is this correct? – Vela

also what happens when you shift by 2 or 3 (or anything >1) bits in the right positive? What does X become? – Vela

"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." perhaps? – Vela

I'm more interested in why retaining the 1s works as intended (divide by 2 even for negative numbers). math.stackexchange.com/questions/4877552/… – Vela

@CharlieParker is my edit ok for you? – Flamsteed

Answer 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 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.

Fung

Can you explain arithmatic shift a little more clearly. And example please? – Portia

@ChandrahasAroori there are tons of examples that you can find on google en.wikipedia.org/wiki/Bitwise_operation – Infective

"11111100 (decimal ~4)" .. isn't that negative of 00000011 or -3 instead ? – Ammo

@Ammo This is 2's complement notation. In order to get 2's complement representation of -4, take the bitwise representation of 4, flip all the bits and add 1. – Simply

Can you explain why "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." works? i.e., I assume it was defined like that so it does x/2 and x*2 roughly regardless of the sign. – Vela

I'm more interested in why retaining the 1s works as intended (divide by 2 even for negative numbers). math.stackexchange.com/questions/4877552/… – Vela

“Logical shift treats the number as a bunch of bits, and shifts in zeros. This is the >> operator in C.” this is not true; how the operator behaves depends on the implementation and whether the operand is signed or unsigned. For nonnegative values of signed type, and for unsigned types, it shifts in 0. For negative values of signed type, the result is implementation defined, which in virtually all cases means that the sign bit is duplicated. So it's more accurate to say C always shifts in the sign bit, if you take unsigned types to have the sign bit implicitly fixed to 0. – Thurmond

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.

Idiom

what if we do 3 bit shifts to the right arithmetic shift? And why is the transformation as is? – Vela

I'm more interested in why retaining the 1s works as intended (divide by 2 even for negative numbers). math.stackexchange.com/questions/4877552/… – Vela

Answer 4

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.

Tetravalent