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

http://www.velocityreviews.com/forums/(E-Mail Removed)lid