Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Two's complement integer divided by Powers of 2 question

Reply
Thread Tools

Two's complement integer divided by Powers of 2 question

 
 
Janice
Guest
Posts: n/a
 
      07-08-2005
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


 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-08-2005
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
 
Reply With Quote
 
 
 
 
Joe Wright
Guest
Posts: n/a
 
      07-09-2005
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
>


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?

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
 
Reply With Quote
 
websnarf@gmail.com
Guest
Posts: n/a
 
      07-09-2005
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?


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.)

--
Paul Hsieh
http://www.pobox.com/~qed/

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
2's complement vs. 1's complement vs. ... Roberto Waltman C Programming 4 06-13-2011 11:26 PM
small integer powers -- use pow() or explicit multiplication? blmblm@myrealbox.com C Programming 22 03-23-2009 12:19 AM
1's complement and 2's complement sarathy C++ 22 08-02-2006 05:53 PM
1's complement and 2's complement sarathy C Programming 20 08-02-2006 05:53 PM
sign magnitude, ones complement, two's complement Mantorok Redgormor C Programming 8 10-07-2003 11:52 PM



Advertisments