2

So I was asked to perform the simple task of doing a 3-bit arithmetic shift of the number 1101 (-3 in 2's complement notation).

Now this is easy and it goes as 1101 -> 1110 -> 1111 -> 1111. So the final result should be 1111 (-1 in 2's complement notation).

However, I also learned that shifting a number p = 3 positions to the right is the same as dividing that number by 2p = 8. Therefore shouldn't my result be 0, since -3 divided by 8 is 0 (with remainder -3).

What am I missing in this apparent paradox?

ocrdu
  • 8,705
  • 21
  • 30
  • 42
Granger Obliviate
  • 1,391
  • 10
  • 29
  • 1
    Please see [Non-equivalence of arithmetic right shift and division](https://en.wikipedia.org/wiki/Arithmetic_shift#Non-equivalence_of_arithmetic_right_shift_and_division). – Andrew Morton Nov 24 '20 at 16:26
  • As a hint, what happens when you use this process to divide -1 by 2? – The Photon Nov 24 '20 at 16:27
  • Arithmetic shift right is not the same as logical shift right – Marko Buršič Nov 24 '20 at 16:31
  • 2
    Interesting question . Division by 2 by shifting right is more like divide by 2 followed by 'floor' operation. ie., For eg: -0.5 gets rounded to -1, while +0.5 gets rounded to 0. – Mitu Raj Nov 27 '20 at 12:07

2 Answers2

12

Right shifting of a negative two's complement number is indeed equivalent to division as you stated, but always rounding down (towards minus infinity). So no paradox here - division of -1 by 2 gives -0.5 which is rounded down to the same -1.

P.S. The rounding down is also true for positive numbers shifted.

Eugene Sh.
  • 9,986
  • 2
  • 26
  • 41
7

Shifting right is dividing by two and rounding down.

So -3 / 2 = -1.5, rounded down to -2. -2 / 2 = -1, rounded down to -1. -1 / 2 = -0.5, rounded down to -1.

Simon Richter
  • 12,031
  • 1
  • 23
  • 49