1
\$\begingroup\$

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 2^p=8. Therefore shouldn't my result be 0, since -3 dividing by 8 is 0 (with remainder -3). What am I missing in this apparent paradox?

\$\endgroup\$
4
  • \$\begingroup\$ Please see Non-equivalence of arithmetic right shift and division. \$\endgroup\$ – Andrew Morton Nov 24 '20 at 16:26
  • \$\begingroup\$ As a hint, what happens when you use this process to divide -1 by 2? \$\endgroup\$ – The Photon Nov 24 '20 at 16:27
  • \$\begingroup\$ Arithmetic shift right is not the same as logical shift right \$\endgroup\$ – Marko Buršič Nov 24 '20 at 16:31
  • \$\begingroup\$ 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. \$\endgroup\$ – Mitu Raj Nov 27 '20 at 12:07
8
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.