Two's complement integer divided by Powers of 2 question

[Janice]

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

 

[Eric Sosman]

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.

 

[Joe Wright]

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

Note that pow(2,k) is a double. Division of integer by double is done in
floating point and yields double. What are you trying to do? What do you
think the "correct answer" to any of this is?

 

[websnarf]

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?

This is a bit involved.

1) Floating point rounds towards zero, whereas right shifting usually
rounds towards INT_MIN. (Using pow(2,k) forces promotion to floating
point.)

2) The ANSI C standard does not dictate anything useful about how right
shift works. Basically some old obsolete hardware that the ANSI C
standard committee insists on continuing to coddle cannot perform
correct right shifting. Rather than forcing that very marginal old
hardware to emulate the correct behavior (much as they forced the most
popular microprocessor family of all time, and widely deployed
desktop/workstation processor in history to emulate FP before they
could manage to include on-chip support for it) for this less commonly
used operation, the standard just decided not to define a single
behavior for it.

So whether or not some calculation is equal or consistant with right
shift is not up to the numerical or mathematical properties of ordinary
calculations. Its actually up to the capriciousness of the compiler
implementor. (Though its not surprising that your textbook thinks this
behavior deterministic, since 99.9999999% of all platforms do perform
correctly.)