Rounding during division

Discussion in 'C Programming' started by Christopher Key, Sep 12, 2007.

  1. Hello,

    Could anyone tell me what the various C standards say on the subject of
    rounding during signed integer division. On my system, it always rounds
    towards 0:

    printf("%d", 3/2); // 1
    printf("%d", 1/2); // 0
    printf("%d", -1/2); // 0
    printf("%d", -3/2); // -1

    Can I rely on this always being the case?


    Secondly, is there anything that I can rely when right shifting a
    negative int32_t. Given that int32_t is guaranteed to be stored in
    two's complement format, can it be assumed that right shifting by N is
    the same as division by 2^N with rounding towards -inf? e.g:

    printf("%d", 3>>1); // 1
    printf("%d", 1>>1); // 0
    printf("%d", -1>>1); // -1
    printf("%d", -3>>1); // -3

    If bitwise operations have undefined behaviour on negative intN_t types,
    what was the point in specifying that they must be in two's complement
    format?

    Regards,

    Chris
     
    Christopher Key, Sep 12, 2007
    #1
    1. Advertising

  2. Christopher Key

    Army1987 Guest

    On Wed, 12 Sep 2007 13:39:26 +0100, Christopher Key wrote:

    > Hello,
    >
    > Could anyone tell me what the various C standards say on the subject of
    > rounding during signed integer division. On my system, it always rounds
    > towards 0:
    >
    > printf("%d", 3/2); // 1
    > printf("%d", 1/2); // 0
    > printf("%d", -1/2); // 0
    > printf("%d", -3/2); // -1
    >
    > Can I rely on this always being the case?

    Yes.

    > Secondly, is there anything that I can rely when right shifting a
    > negative int32_t. Given that int32_t is guaranteed to be stored in
    > two's complement format, can it be assumed that right shifting by N is
    > the same as division by 2^N with rounding towards -inf? e.g:
    >
    > printf("%d", 3>>1); // 1
    > printf("%d", 1>>1); // 0
    > printf("%d", -1>>1); // -1
    > printf("%d", -3>>1); // -3
    >
    > If bitwise operations have undefined behaviour on negative intN_t types,
    > what was the point in specifying that they must be in two's complement
    > format?


    Bitwise shifts on signed integers are implementation defined. For
    example the sign bit may be treated differently.
    --
    Army1987 (Replace "NOSPAM" with "email")
    If you're sending e-mail from a Windows machine, turn off Microsoft's
    stupid “Smart Quotes†feature. This is so you'll avoid sprinkling garbage
    characters through your mail. -- Eric S. Raymond and Rick Moen
     
    Army1987, Sep 12, 2007
    #2
    1. Advertising

  3. Army1987 wrote:

    > On Wed, 12 Sep 2007 13:39:26 +0100, Christopher Key wrote:
    >
    >> Hello,
    >>
    >> Could anyone tell me what the various C standards say on the
    >> subject of rounding during signed integer division. On my
    >> system, it always rounds towards 0:
    >>
    >> printf("%d", 3/2); // 1
    >> printf("%d", 1/2); // 0
    >> printf("%d", -1/2); // 0
    >> printf("%d", -3/2); // -1
    >>
    >> Can I rely on this always being the case?

    > Yes.


    No. That is only true for C99.
    There are still many C89-C95 implementations and they were
    allowed to make their own decision:

    | If either operand is negative, whether the
    | result of the / operator is the largest integer less than the
    | algebraic quotient or the smallest integer greater than the
    | algebraic quotient is implementation-defined, as is the sign
    | of the result of the % operator.

    Ralf
     
    Ralf Damaschke, Sep 12, 2007
    #3
  4. On Wed, 12 Sep 2007 15:13:04 +0200, in comp.lang.c , Army1987
    <> wrote:

    >On Wed, 12 Sep 2007 13:39:26 +0100, Christopher Key wrote:
    >
    >> Hello,
    >>
    >> Could anyone tell me what the various C standards say on the subject of
    >> rounding during signed integer division. On my system, it always rounds
    >> towards 0:
    >>
    >> printf("%d", 3/2); // 1
    >> printf("%d", 1/2); // 0
    >> printf("%d", -1/2); // 0
    >> printf("%d", -3/2); // -1
    >>
    >> Can I rely on this always being the case?

    >Yes.


    No. For the positive cases, you can rely on it. For the negative
    cases, compilers may round up or down, depending on which version of
    the C standard they comply to.
    --
    Mark McIntyre

    "Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are,
    by definition, not smart enough to debug it."
    --Brian Kernighan
     
    Mark McIntyre, Sep 12, 2007
    #4
  5. Christopher Key

    Old Wolf Guest

    On Sep 13, 1:13 am, Army1987 <> wrote:
    > On Wed, 12 Sep 2007 13:39:26 +0100, Christopher Key wrote:
    > > Could anyone tell me what the various C standards say on the subject of
    > > rounding during signed integer division. On my system, it always rounds
    > > towards 0:

    >
    > > Can I rely on this always being the case?

    >
    > Yes.


    In fact it is implementation-defined in C90, whether it
    rounds up or down for negative intergers.

    > Bitwise shifts on signed integers are implementation defined.


    No. There are four cases:
    1. Right-shift of non-negative value: well-defined
    2. Right-shift of negative value: implementation-defined
    3. Left-shift of negative value: undefined
    4. Left-shift of non-negative value: undefined if the
    shift would cause an overflow, otherwise well-defined
     
    Old Wolf, Sep 13, 2007
    #5
  6. Old Wolf wrote:
    > On Sep 13, 1:13 am, Army1987 <> wrote:
    >> On Wed, 12 Sep 2007 13:39:26 +0100, Christopher Key wrote:
    >>> Could anyone tell me what the various C standards say on the subject of
    >>> rounding during signed integer division. On my system, it always rounds
    >>> towards 0:
    >>> Can I rely on this always being the case?

    >> Yes.

    >
    > In fact it is implementation-defined in C90, whether it
    > rounds up or down for negative intergers.
    >
    >> Bitwise shifts on signed integers are implementation defined.

    >
    > No. There are four cases:
    > 1. Right-shift of non-negative value: well-defined
    > 2. Right-shift of negative value: implementation-defined
    > 3. Left-shift of negative value: undefined
    > 4. Left-shift of non-negative value: undefined if the
    > shift would cause an overflow, otherwise well-defined
    >


    Thanks,

    Is there any clean, portable way of acheiving signed integer division by
    a power of 2 with rounding towards -inf (under C99). gcc guarantees
    that right-shifts on a signed integer will always give this behaviour,
    and I'm guessing that pretty much any code compiled for a target with an
    ASR instruction will do the same, but I really don't want the code to
    silently break for compilers that don't.

    The options seem to be:

    1) Discover how right shift of negative values is implemented using
    preprocessor macros and issue an error at compile time if required. I
    don't think this is possible, although a useful extension to the C
    standard might be to force the provision of macros that allow code to
    determine how implementation defined behaviour has been implemented.

    2) Check the compiler against a list of known okay compilers. This
    seems very messy.

    3) Write code that manually implements the required behaviour, e.g.:

    x = (x & ~3) / 4

    It seems a little hopeful to assume that the compiler would be able to
    optimise this into an arithmetic shift though, and it's certainly not as
    self documenting.

    Any thoughts?

    Regards,

    Chris
     
    Christopher Key, Sep 17, 2007
    #6
  7. On Sep 17, 4:18 am, Christopher Key <> wrote:
    > Is there any clean, portable way of acheiving signed integer division by
    > a power of 2 with rounding towards -inf (under C99). gcc guarantees
    > that right-shifts on a signed integer will always give this behaviour,
    > and I'm guessing that pretty much any code compiled for a target with an
    > ASR instruction will do the same, but I really don't want the code to
    > silently break for compilers that don't.
    >
    > The options seem to be:
    >
    > 1) Discover how right shift of negative values is implemented using
    > preprocessor macros and issue an error at compile time if required. I
    > don't think this is possible, although a useful extension to the C
    > standard might be to force the provision of macros that allow code to
    > determine how implementation defined behaviour has been implemented.


    typedef int assertion_dummy_array[(-value >> shiftbits == othervalue)
    * 2 - 1];

    If the condition given in the parentheses evaluates to false (0), then
    the array typedef will have a negative size, which should issue a
    compiler diagnostic.
     
    Justin Spahr-Summers, Sep 17, 2007
    #7
  8. "Justin Spahr-Summers" <> a écrit dans le
    message de news: ...
    > On Sep 17, 4:18 am, Christopher Key <> wrote:
    >> Is there any clean, portable way of acheiving signed integer division by
    >> a power of 2 with rounding towards -inf (under C99). gcc guarantees
    >> that right-shifts on a signed integer will always give this behaviour,
    >> and I'm guessing that pretty much any code compiled for a target with an
    >> ASR instruction will do the same, but I really don't want the code to
    >> silently break for compilers that don't.
    >>
    >> The options seem to be:
    >>
    >> 1) Discover how right shift of negative values is implemented using
    >> preprocessor macros and issue an error at compile time if required. I
    >> don't think this is possible, although a useful extension to the C
    >> standard might be to force the provision of macros that allow code to
    >> determine how implementation defined behaviour has been implemented.

    >
    > typedef int assertion_dummy_array[(-value >> shiftbits == othervalue)
    > * 2 - 1];
    >
    > If the condition given in the parentheses evaluates to false (0), then
    > the array typedef will have a negative size, which should issue a
    > compiler diagnostic.


    Of course you can test implementation defined behaviour at run time and at
    compile time in this case (call it static_assert).
    But you want to do this at the preprocessing stage in order to select the
    proper code for the implementation. There is no guarantee that the
    preprocessor use the same arithmetics as the target, so you cannot rely on
    #if (-1 >> 1) == -1 for instance. One would need explicit macros along the
    lines of INT_MAX to detect what type of integer representation is used, what
    type of arithmetics, and so on.

    --
    Chqrlie.
     
    Charlie Gordon, Sep 18, 2007
    #8
  9. Justin Spahr-Summers wrote:
    > On Sep 17, 4:18 am, Christopher Key <> wrote:
    >> Is there any clean, portable way of acheiving signed integer division by
    >> a power of 2 with rounding towards -inf (under C99). gcc guarantees
    >> that right-shifts on a signed integer will always give this behaviour,
    >> and I'm guessing that pretty much any code compiled for a target with an
    >> ASR instruction will do the same, but I really don't want the code to
    >> silently break for compilers that don't.
    >>
    >> The options seem to be:
    >>
    >> 1) Discover how right shift of negative values is implemented using
    >> preprocessor macros and issue an error at compile time if required. I
    >> don't think this is possible, although a useful extension to the C
    >> standard might be to force the provision of macros that allow code to
    >> determine how implementation defined behaviour has been implemented.

    >
    > typedef int assertion_dummy_array[(-value >> shiftbits == othervalue)
    > * 2 - 1];
    >
    > If the condition given in the parentheses evaluates to false (0), then
    > the array typedef will have a negative size, which should issue a
    > compiler diagnostic.
    >


    I'll give that a go. It'd be interesting to know how many compilers
    warn correctly in all cases, even when cross compiling for a platform
    with different shift instructions available to those on the host.

    Regards,

    Chris
     
    Christopher Key, Sep 18, 2007
    #9
  10. Charlie Gordon wrote:
    > "Justin Spahr-Summers" <> a écrit dans le
    > message de news: ...
    >> On Sep 17, 4:18 am, Christopher Key <> wrote:
    >>> Is there any clean, portable way of acheiving signed integer division by
    >>> a power of 2 with rounding towards -inf (under C99). gcc guarantees
    >>> that right-shifts on a signed integer will always give this behaviour,
    >>> and I'm guessing that pretty much any code compiled for a target with an
    >>> ASR instruction will do the same, but I really don't want the code to
    >>> silently break for compilers that don't.
    >>>
    >>> The options seem to be:
    >>>
    >>> 1) Discover how right shift of negative values is implemented using
    >>> preprocessor macros and issue an error at compile time if required. I
    >>> don't think this is possible, although a useful extension to the C
    >>> standard might be to force the provision of macros that allow code to
    >>> determine how implementation defined behaviour has been implemented.

    >> typedef int assertion_dummy_array[(-value >> shiftbits == othervalue)
    >> * 2 - 1];
    >>
    >> If the condition given in the parentheses evaluates to false (0), then
    >> the array typedef will have a negative size, which should issue a
    >> compiler diagnostic.

    >
    > Of course you can test implementation defined behaviour at run time and at
    > compile time in this case (call it static_assert).
    > But you want to do this at the preprocessing stage in order to select the
    > proper code for the implementation. There is no guarantee that the
    > preprocessor use the same arithmetics as the target, so you cannot rely on
    > #if (-1 >> 1) == -1 for instance. One would need explicit macros along the
    > lines of INT_MAX to detect what type of integer representation is used, what
    > type of arithmetics, and so on.
    >


    Presumably, all that INT_MAX and INT_MIN will tell you is whether you're
    using a two's complement machine or not, and there's no guarantee that a
    specific shift behaviour has been implemented.

    I guess that the safest way is to simply perform a runtime check.

    Regards,

    Chris
     
    Christopher Key, Sep 18, 2007
    #10
  11. "Christopher Key" <> a écrit dans le message de news:
    46efb320$0$21085$...
    > Charlie Gordon wrote:
    >> "Justin Spahr-Summers" <> a écrit dans le
    >> message de news: ...
    >>> On Sep 17, 4:18 am, Christopher Key <> wrote:
    >>>> Is there any clean, portable way of acheiving signed integer division
    >>>> by
    >>>> a power of 2 with rounding towards -inf (under C99). gcc guarantees
    >>>> that right-shifts on a signed integer will always give this behaviour,
    >>>> and I'm guessing that pretty much any code compiled for a target with
    >>>> an
    >>>> ASR instruction will do the same, but I really don't want the code to
    >>>> silently break for compilers that don't.
    >>>>
    >>>> The options seem to be:
    >>>>
    >>>> 1) Discover how right shift of negative values is implemented using
    >>>> preprocessor macros and issue an error at compile time if required. I
    >>>> don't think this is possible, although a useful extension to the C
    >>>> standard might be to force the provision of macros that allow code to
    >>>> determine how implementation defined behaviour has been implemented.
    >>> typedef int assertion_dummy_array[(-value >> shiftbits == othervalue)
    >>> * 2 - 1];
    >>>
    >>> If the condition given in the parentheses evaluates to false (0), then
    >>> the array typedef will have a negative size, which should issue a
    >>> compiler diagnostic.

    >>
    >> Of course you can test implementation defined behaviour at run time and
    >> at compile time in this case (call it static_assert).
    >> But you want to do this at the preprocessing stage in order to select the
    >> proper code for the implementation. There is no guarantee that the
    >> preprocessor use the same arithmetics as the target, so you cannot rely
    >> on #if (-1 >> 1) == -1 for instance. One would need explicit macros
    >> along the lines of INT_MAX to detect what type of integer representation
    >> is used, what type of arithmetics, and so on.
    >>

    >
    > Presumably, all that INT_MAX and INT_MIN will tell you is whether you're
    > using a two's complement machine or not, and there's no guarantee that a
    > specific shift behaviour has been implemented.
    >
    > I guess that the safest way is to simply perform a runtime check.


    Except c99 6.5.7 specifies that sight shifting a signed type with negative
    value results in an implementation defined result but does not give an
    exhaustive list of possible implementations. To correctly detect at runtime
    a given 'expected' behaviour (such as ARS or LSR) one would need to conduct
    an exhaustive test of all possible shift operands. Furthermore,
    implementation defined behaviour includes terminating the program (a known
    characteristic of the DS9K)

    Definitely, a few macros in stdint specifying INT_RIGHT_SHIFT_IS_SIGNED or
    similar could help. The same goes for macros telling about integer
    representation and other signed arithmetic specifics.

    --
    Chqrlie.
     
    Charlie Gordon, Sep 18, 2007
    #11
  12. Christopher Key

    CBFalconer Guest

    Charlie Gordon wrote:
    >

    .... snip ...
    >
    > Except c99 6.5.7 specifies that sight shifting a signed type with
    > negative value results in an implementation defined result but
    > does not give an exhaustive list of possible implementations. To
    > correctly detect at runtime a given 'expected' behaviour (such as
    > ARS or LSR) one would need to conduct an exhaustive test of all
    > possible shift operands. Furthermore, implementation defined
    > behaviour includes terminating the program (a known characteristic
    > of the DS9K)


    Check your supplier. Your DS9K lacks the latest improvements. Mine,
    in the same circumstances, submits a fake tax return to the IRS,
    with flags that ensure the IRS pulls it for examination. The fake
    return has material that proves you hid 10,000,000 USD (or more)
    income last year, and makes you liable for the tax, penalties,
    etc.

    After this action the machine terminates, after wiping out all
    traces of actions taken since the (attempted) right shift of a
    negative value.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Sep 18, 2007
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. walala
    Replies:
    12
    Views:
    1,876
  2. sunwij

    FLOATING POINT DIVISION

    sunwij, Dec 28, 2003, in forum: VHDL
    Replies:
    3
    Views:
    1,031
    sunwij
    Dec 29, 2003
  3. Replies:
    94
    Views:
    4,498
    ¬a\\/b
    Feb 9, 2007
  4. traveller
    Replies:
    0
    Views:
    1,194
    traveller
    Jan 8, 2008
  5. Dmitry Korolyov

    Datagrid not updated during delete, but updated during insert and update

    Dmitry Korolyov, Sep 22, 2003, in forum: ASP .Net Datagrid Control
    Replies:
    0
    Views:
    416
    Dmitry Korolyov
    Sep 22, 2003
Loading...

Share This Page