Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Rounding during division

Reply
Thread Tools

Rounding during division

 
 
Christopher Key
Guest
Posts: n/a
 
      09-12-2007
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
 
Reply With Quote
 
 
 
 
Army1987
Guest
Posts: n/a
 
      09-12-2007
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

 
Reply With Quote
 
 
 
 
Ralf Damaschke
Guest
Posts: n/a
 
      09-12-2007
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
 
Reply With Quote
 
Mark McIntyre
Guest
Posts: n/a
 
      09-12-2007
On Wed, 12 Sep 2007 15:13:04 +0200, in comp.lang.c , Army1987
<(E-Mail Removed)> 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
 
Reply With Quote
 
Old Wolf
Guest
Posts: n/a
 
      09-13-2007
On Sep 13, 1:13 am, Army1987 <(E-Mail Removed)> 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

 
Reply With Quote
 
Christopher Key
Guest
Posts: n/a
 
      09-17-2007
Old Wolf wrote:
> On Sep 13, 1:13 am, Army1987 <(E-Mail Removed)> 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
 
Reply With Quote
 
Justin Spahr-Summers
Guest
Posts: n/a
 
      09-17-2007
On Sep 17, 4:18 am, Christopher Key <(E-Mail Removed)> 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.

 
Reply With Quote
 
Charlie Gordon
Guest
Posts: n/a
 
      09-18-2007
"Justin Spahr-Summers" <(E-Mail Removed)> a crit dans le
message de news: (E-Mail Removed) om...
> On Sep 17, 4:18 am, Christopher Key <(E-Mail Removed)> 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.


 
Reply With Quote
 
Christopher Key
Guest
Posts: n/a
 
      09-18-2007
Justin Spahr-Summers wrote:
> On Sep 17, 4:18 am, Christopher Key <(E-Mail Removed)> 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
 
Reply With Quote
 
Christopher Key
Guest
Posts: n/a
 
      09-18-2007
Charlie Gordon wrote:
> "Justin Spahr-Summers" <(E-Mail Removed)> a crit dans le
> message de news: (E-Mail Removed) om...
>> On Sep 17, 4:18 am, Christopher Key <(E-Mail Removed)> 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
 
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
Warning during generating classes through WSIMPORT & Error during xmlvalidation traveller Java 0 01-08-2008 07:00 AM
division by 7 without using division operator krypto.wizard@gmail.com C Programming 94 02-09-2007 06:57 AM
rounding to integer valentin tihomirov VHDL 2 02-16-2004 10:07 AM
Datagrid not updated during delete, but updated during insert and update Dmitry Korolyov ASP .Net Datagrid Control 0 09-22-2003 10:57 AM
will Synposys Design Compiler support division by two's power and integer rounding? walala VHDL 12 09-14-2003 03:49 PM



Advertisments