Janice wrote:
I got this question from my textbook and I cannot understand the theory.
When a signed positive integer X divided by pow(2,k), the result is shifting
k bits to right and putting w-k bits of 0 from the most significant bits.
However, when the X is a negative number divided by pow(2,k), the shifting
and sign bit extension method doesnt give the correct answer?
What kind of bias should we make on the X before the division?
Thanx
The "theory" is simple enough. Let's work through
the example of dividing -6 by 2. In two's complement,
-6 looks like 11...1010. Shifting this right one bit
position and inserting a new 1 in the vacated leftmost
spot gives 11...1101, which is -3, half of -6. Everything
looks good so far.
But now if we try the same thing starting with -3,
things don't work quite so well. Doing another shift
produces 11...1110, which is -2. However, the result
of the integer division -3/2 is not -2, but -1: Integer
division discards the fractional part of the "true" quotient,
so we get -3/2 => -1.5 => -1. (Historical note: the first
C Standard didn't define integer division quite so rigidly,
and allowed -3/2 to be either -2 or -1. The latest Standard
has tightened the rules to follow the practice adopted by
other programming languages.)
You can probably see what's happening: integer division
"truncates toward zero" while right-shifting "truncates toward
minus infinity." For even X there's nothing to truncate and
you'll get the same answer either way, and for positive X
zero is in the same direction as minus infinity. But for odd
negative X, zero and minus infinity are in opposite directions
and the two operations give different answers.
There's a further complication: C doesn't define what
happens when a negative number is right-shifted. This is a
nod toward different instruction sets on different machines:
some will fill the vacated sign position with a copy of the
original sign bit, while others will fill with a zero bit
(these are sometimes called "arithmetic shift" and "logical
shift" operations). Right-shifting -6 and supplying a new
zero bit would transform 11...1010 to 01...0101, a large
positive number which is clearly not a good approximation
to -3! The C Standard doesn't even require that either of
these results be obtained; it simply says "all bets are off"
if you right-shift a negative number.
--
Eric Sosman
es*****@acm-dot-org.invalid
