Two's complement integer divided by Powers of 2 question

Discussion in 'C Programming' started by Janice, Jul 8, 2005.

  1. Janice

    Janice Guest

    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?
    Janice, Jul 8, 2005
    1. Advertisements

  2. Janice

    Eric Sosman Guest

    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, Jul 8, 2005
    1. Advertisements

  3. Janice

    Joe Wright Guest

    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, Jul 9, 2005
  4. Janice

    websnarf Guest

    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

    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
    websnarf, Jul 9, 2005
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.