Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Direct computation of integer limits in K&R2?

Reply
Thread Tools

Direct computation of integer limits in K&R2?

 
 
Peter Nilsson
Guest
Posts: n/a
 
      03-12-2008
Ark Khasin <(E-Mail Removed)> wrote:
> Peter Nilsson wrote:
> > Quoting pete:
> >
> > * #if !(1 & -1)
> > * * * printf("ones complement\n");
> > * #elif -1 & 2
> > * * * printf("twos complement\n");
> > * #else
> > * * * printf("sign magnitude\n");
> > * #endif
> >
> > Pete asked if greycode or other weird representations
> > could be used for negative integers, but it seems that
> > is not so, despite the loose wording of C90.
> > [cf <http://groups.google.com/group/comp.std.c/msg/5f332b9aa22b92ec>]

>
> Is there any assurance that the representation of integer
> constants in the preprocessor is in any way related to the
> representation of integer objects
> - falls into one of the three models of representation of
> integer objects
> ?


Notionally, yes.

C89 draft 3.8.1

The resulting tokens comprise the controlling constant
expression which is evaluated according to the rules of
$3.4 using arithmetic that has at least the ranges
specified in $2.2.4.2, except that int and unsigned int
act as if they have the same representation as,
respectively, long and unsigned long .

There's similar wording for C99 though intmax_t and uintmax_t
are used.

Unfortunately, many implementations are somewhat inconsistent.
Consider...

#include <limits.h>
#include <stdio.h>

int main(void)
{
printf("ULONG_MAX = %lu\n", ULONG_MAX);

#if -1 == -1ul
puts("-1 == -1ul [pre]");
#endif

if (-1 == -1ul)
puts("-1 == -1ul");

#if 4294967295 == -1ul
puts("4294967295 == -1ul [pre]");
#endif

if (4294967295 == -1ul)
puts("4294967295 == -1ul");

return 0;
}

The output for me using delorie gcc 4.2.1 with -ansi
-pedantic is...

ULONG_MAX = 4294967295
-1 == -1ul [pre]
-1 == -1ul
4294967295 == -1ul

As you can see, there is a discrepancy between the way
that preprocessor arithmetic is evaluated. Fact is,
gcc is not the only compiler to show problems.

> [Of course the above can be repaired so as to not use the
> preprocessor. Just asking...]


Indeed, using the expressions in a normal 'if' would be
the go. There's no reason why say int couldn't use 2c but
long uses 1c.

--
Peter
 
Reply With Quote
 
 
 
 
Micah Cowan
Guest
Posts: n/a
 
      03-12-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) writes:

> On Mar 11, 7:30 pm, Micah Cowan <(E-Mail Removed)> wrote:
>> Flash Gordon <(E-Mail Removed)> writes:
>> > Even if you know it is 2s complement you still can't do it. You need
>> > to know whether sign bit = 1 and all value bits = 0 is a trap or not
>> > since it is allowed to be a trap representation.

>>
>> It's only allowed to be a trap representation on _non_ two's
>> complement representations. sign bit = 1 and all value bits = 0 (and
>> padding bits at non-trap values) would necessarily be the minimum
>> representable value.

>
> 6.5.6.2p2 says ("the first two" below are sign-and-magnitude and
> two's complement):
>
> "Which of these applies is implementation-defined, as is whether the
> value with sign bit 1 and all value bits zero (for the first two),
> or with sign bit and all value bits 1 (for ones' complement), is a
> trap representation or a normal value."


Huh. I managed to forget that somehow. My bad, Flash.

--
Micah J. Cowan
Programmer, musician, typesetting enthusiast, gamer...
http://micah.cowan.name/
 
Reply With Quote
 
 
 
 
Ark Khasin
Guest
Posts: n/a
 
      03-12-2008
Peter Nilsson wrote:
> Ark Khasin <(E-Mail Removed)> wrote:
>> Peter Nilsson wrote:
>>> Quoting pete:
>>>
>>> #if !(1 & -1)
>>> printf("ones complement\n");
>>> #elif -1 & 2
>>> printf("twos complement\n");
>>> #else
>>> printf("sign magnitude\n");
>>> #endif
>>>
>>> Pete asked if greycode or other weird representations
>>> could be used for negative integers, but it seems that
>>> is not so, despite the loose wording of C90.
>>> [cf <http://groups.google.com/group/comp.std.c/msg/5f332b9aa22b92ec>]

>> Is there any assurance that the representation of integer
>> constants in the preprocessor is in any way related to the
>> representation of integer objects
>> - falls into one of the three models of representation of
>> integer objects
>> ?

>
> Notionally, yes.
>
> C89 draft 3.8.1
>
> The resulting tokens comprise the controlling constant
> expression which is evaluated according to the rules of
> $3.4 using arithmetic that has at least the ranges
> specified in $2.2.4.2, except that int and unsigned int
> act as if they have the same representation as,
> respectively, long and unsigned long .
>
> There's similar wording for C99 though intmax_t and uintmax_t
> are used.
>
> Unfortunately, many implementations are somewhat inconsistent.
> Consider...
>
> #include <limits.h>
> #include <stdio.h>
>
> int main(void)
> {
> printf("ULONG_MAX = %lu\n", ULONG_MAX);
>
> #if -1 == -1ul
> puts("-1 == -1ul [pre]");
> #endif
>
> if (-1 == -1ul)
> puts("-1 == -1ul");
>
> #if 4294967295 == -1ul
> puts("4294967295 == -1ul [pre]");
> #endif
>
> if (4294967295 == -1ul)
> puts("4294967295 == -1ul");
>
> return 0;
> }
>
> The output for me using delorie gcc 4.2.1 with -ansi
> -pedantic is...
>
> ULONG_MAX = 4294967295
> -1 == -1ul [pre]
> -1 == -1ul
> 4294967295 == -1ul
>
> As you can see, there is a discrepancy between the way
> that preprocessor arithmetic is evaluated. Fact is,
> gcc is not the only compiler to show problems.
>
>> [Of course the above can be repaired so as to not use the
>> preprocessor. Just asking...]

>
> Indeed, using the expressions in a normal 'if' would be
> the go. There's no reason why say int couldn't use 2c but
> long uses 1c.
>


Wow. I haven't thought of this possibility. It would imply malicious
intent of the implementer for it have an overhead in simplest
conversions. And it won't be for all markets
But I don't see why such a horror implementation would be illegal.
Thank you for the example.
-- Ark
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      03-12-2008
On Mar 11, 3:01*pm, santosh <(E-Mail Removed)> wrote:
> Peter Nilsson wrote:
> > santosh <(E-Mail Removed)> wrote:
> >> In K&R2 one exercise asks the reader to compute and
> >> print the limits for the basic integer types. This is
> >> trivial for unsigned types. But is it possible for
> >> signed types without invoking undefined behaviour
> >> triggered by overflow? Remember that the constants
> >> in limits.h cannot be used.

>
> > Yes. Unlike C99, unsigned to signed integer conversion
> > is implementation defined without the possibility of
> > raising a signal. So...

>
> > <http://groups.google.com/group/comp.lang.c/msg/ffe17c645660b76c>

>
> > INT_MIN isn't computed per se, rather it's derived by
> > determining the representation for negative ints. [I
> > know pete posted some very simple constant expressions,
> > though it was some time ago.]

>
> Would you say that this exercise is overly complex for that point in
> K&R2?


I will be pretty amazed to see anyone write a portable solution that
does it all (floating point is also requested).
I guess that signed integer <TYPE>_MIN values will be hard to come up
with.

Will computation of DBL_MAX signal a floating point exception?

I guess that it is the hardest exercise in the whole book, by far.
 
Reply With Quote
 
Flash Gordon
Guest
Posts: n/a
 
      03-12-2008
Micah Cowan wrote, On 12/03/08 00:30:
> Flash Gordon <(E-Mail Removed)> writes:
>
>> Ian Collins wrote, On 11/03/08 21:54:
>>> santosh wrote:
>>>> Ian Collins wrote:
>>>>
>>>>> santosh wrote:
>>>>>> Hello all,
>>>>>>
>>>>>> In K&R2 one exercise asks the reader to compute and print the limits
>>>>>> for the basic integer types. This is trivial for unsigned types. But
>>>>>> is it possible for signed types without invoking undefined behaviour
>>>>>> triggered by overflow? Remember that the constants in limits.h cannot
>>>>>> be used.
>>>>>>
>>>>> Isn't it possible to calculate this based on the unsigned types of the
>>>>> same size?
>>>> Won't this require knowledge of the encoding used, whether twos
>>>> complement or sign and magnitude etc?
>>>>
>>> I think so, I should have added that.

>> Even if you know it is 2s complement you still can't do it. You need
>> to know whether sign bit = 1 and all value bits = 0 is a trap or not
>> since it is allowed to be a trap representation.

>
> It's only allowed to be a trap representation on _non_ two's
> complement representations. sign bit = 1 and all value bits = 0 (and
> padding bits at non-trap values) would necessarily be the minimum
> representable value.


Wrong. The C standard explicitly allows for it to be a trap
representation on two's complement representations. Quoting from N1256...

| ... If the sign bit is one, the value shall be modified in one of
| the following ways:
| — the corresponding value with sign bit 0 is negated (sign and
| magnitude);
| — the sign bit has the value −(2 N ) (two’s complement);
| — the sign bit has the value −(2 N − 1) (ones’ complement ).
| Which of these applies is implementation-defined, as is whether the
| value with sign bit 1 and all value bits zero (for the first two), or
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^
| with sign bit and all value bits 1 (for ones’ complement), is a trap
| representation or a normal value. In the case of sign and magnitude
| and ones’ complement, if this representation is a normal value it is
| called a negative zero.

two's complement is one of the first two.

The above is from section 6.2.6.2 para 2.
--
Flash Gordon
 
Reply With Quote
 
Flash Gordon
Guest
Posts: n/a
 
      03-12-2008
Micah Cowan wrote, On 12/03/08 05:55:
> (E-Mail Removed) writes:
>
>> On Mar 11, 7:30 pm, Micah Cowan <(E-Mail Removed)> wrote:
>>> Flash Gordon <(E-Mail Removed)> writes:


<snip trap representation in 2s complement>

> Huh. I managed to forget that somehow. My bad, Flash.


It's easy to forget. I'm not actually aware of any implementations which
make use of this freedom.
--
Flash Gordon
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      03-12-2008
On Mar 11, 2:37*pm, santosh <(E-Mail Removed)> wrote:
> Hello all,
>
> In K&R2 one exercise asks the reader to compute and print the limits for
> the basic integer types. This is trivial for unsigned types. But is it
> possible for signed types without invoking undefined behaviour
> triggered by overflow? Remember that the constants in limits.h cannot
> be used.


You can use shifting to determine how many bits there are in the given
signed integral type. Start with 1 and keep shifting it left until it
drops off. With that information, you can construct the greatest
possible positive integer value: which is all 1's except for the sign
bit, which is zero. The greatest possible negative value is either the
additive inverse of that value, or, in the case of two's complement,
that value less one. You can detect whether two's complement is in
effect by applying a simple test to the value -1:

switch (-1 & 3) {
case 1: /* ...01: sign magnitude */
break;
case 2: /* ...10: one's complement */
break;
case 3: /* ...11: two's complement */
break;
}

That's the general approach I'd take to the exercise.




 
Reply With Quote
 
ymuntyan@gmail.com
Guest
Posts: n/a
 
      03-12-2008
On Mar 12, 2:35 pm, Kaz Kylheku <(E-Mail Removed)> wrote:
> On Mar 11, 2:37 pm, santosh <(E-Mail Removed)> wrote:
>
> > Hello all,

>
> > In K&R2 one exercise asks the reader to compute and print the limits for
> > the basic integer types. This is trivial for unsigned types. But is it
> > possible for signed types without invoking undefined behaviour
> > triggered by overflow? Remember that the constants in limits.h cannot
> > be used.

>
> You can use shifting to determine how many bits there are in the given
> signed integral type. Start with 1 and keep shifting it left until it
> drops off.


That's UB, no?

> With that information, you can construct the greatest
> possible positive integer value: which is all 1's except for the sign
> bit, which is zero. The greatest possible negative value is either the
> additive inverse of that value, or, in the case of two's complement,
> that value less one.


And this may be a trap representation.

Yevgen
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-12-2008
Ark Khasin wrote:
> Peter Nilsson wrote:
>

.... snip ...
>>
>> Unfortunately, many implementations are somewhat inconsistent.
>> Consider...
>>
>> #include <limits.h>
>> #include <stdio.h>
>>
>> int main(void) {
>> printf("ULONG_MAX = %lu\n", ULONG_MAX);
>>
>> #if -1 == -1ul
>> puts("-1 == -1ul [pre]");
>> #endif
>>
>> if (-1 == -1ul)
>> puts("-1 == -1ul");
>>
>> #if 4294967295 == -1ul
>> puts("4294967295 == -1ul [pre]");
>> #endif
>>
>> if (4294967295 == -1ul)
>> puts("4294967295 == -1ul");
>> return 0;
>> }
>>
>> The output for me using delorie gcc 4.2.1 with -ansi
>> -pedantic is...
>>
>> ULONG_MAX = 4294967295
>> -1 == -1ul [pre]
>> -1 == -1ul
>> 4294967295 == -1ul
>>
>> As you can see, there is a discrepancy between the way
>> that preprocessor arithmetic is evaluated. Fact is,
>> gcc is not the only compiler to show problems.


What's wrong with that, remembering that (for gcc, on xx86's) a
long is defined to be identical to an int.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-12-2008
Kaz Kylheku wrote:
> santosh <(E-Mail Removed)> wrote:
>>
>> In K&R2 one exercise asks the reader to compute and print the
>> limits for the basic integer types. This is trivial for unsigned
>> types. But is it possible for signed types without invoking
>> undefined behaviour triggered by overflow? Remember that the
>> constants in limits.h cannot be used.

>
> You can use shifting to determine how many bits there are in the
> given signed integral type. Start with 1 and keep shifting it
> left until it drops off. With that information, you can construct

....

No, because the moment it 'drops off' you have run into
implementation (or undefined) behaviour. You can't write portable
code to do this. You can possibly write code that executes on YOUR
machinery.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.




--
Posted via a free Usenet account from http://www.teranews.com

 
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
Function for direct conversion integer > slv aleksazr@gmail.com VHDL 2 12-25-2012 07:22 PM
where can I find good samples for efficient computation of matrix multiplication? walala VHDL 2 03-24-2010 10:06 AM
GPS : Basic pseudo-distance computation le Cl? VHDL 15 04-11-2009 09:22 AM
"Symbolic computation" Jesper Sahner Java 3 12-06-2004 10:41 AM



Advertisments