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

# 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:
> > ... 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

Not necessarily. Non-normalised floating point is one way of
implementing 1c integers. I could imagine that large integers
might theoretically be implemented this way.

[I remember old Macs supporting 80 and 96-bit floating point
types. Such types could be used to implement 64-bit integers
on 16/32 bit machines.]

> for it have an overhead in simplest conversions.

Nevertheless such design decisions are sometimes made.

> And it won't be for all markets But I don't see why such
> a horror implementation would be illegal.

Horror or not, it's just another virtual C machine to me.

--
Peter

Malcolm McLean
Guest
Posts: n/a

 03-12-2008

"santosh" <(E-Mail Removed)> wrote in message
news:fr6u3e\$icr\$(E-Mail Removed)...
> 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.
>

I don't think there's a perfect answer.

However this is the closest I could get.

double x = 0;
int testme;

do
{
x++;
testme = (int) x;
} while((double) testme == x);

printf("Biggest integer %g\n", x - 1);

It will fail if all ints are not exactly representable by a double. Which is
an int 64 machine.
(Wail, gnash).

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Kaz Kylheku
Guest
Posts: n/a

 03-12-2008
On Mar 12, 1:23*pm, (E-Mail Removed) wrote:
> On Mar 12, 2:35 pm, Kaz Kylheku <(E-Mail Removed)> wrote:
> > 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?

Unfortunately it is. Shifting a bit into the sign is UB. Only a
positive value whose double is representable may be shifted left by
one bit.

This means that the sign bit is quite impervious to bit manipulation.

Ben Bacarisse
Guest
Posts: n/a

 03-12-2008
"Malcolm McLean" <(E-Mail Removed)> writes:

> "santosh" <(E-Mail Removed)> wrote in message
> news:fr6u3e\$icr\$(E-Mail Removed)...
>> 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.
>>

> I don't think there's a perfect answer.
>
> However this is the closest I could get.
>
> double x = 0;
> int testme;
>
> do
> {
> x++;
> testme = (int) x;
> } while((double) testme == x);
>
> printf("Biggest integer %g\n", x - 1);

I don't think you need to be so cautious -- ints must use binary, so
you could start at 1 and repeatedly double x and try to convert x-1.
Even so, you have not gained anything -- the conversion to int, when
it is out of range, is still undefined.

--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 03-13-2008
Kaz Kylheku <(E-Mail Removed)> writes:

> On Mar 12, 1:23Â*pm, (E-Mail Removed) wrote:
>> On Mar 12, 2:35 pm, Kaz Kylheku <(E-Mail Removed)> wrote:
>> > 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?

>
> Unfortunately it is. Shifting a bit into the sign is UB. Only a
> positive value whose double is representable may be shifted left by
> one bit.
>
> This means that the sign bit is quite impervious to bit
> manipulation.

It must participate in other bit operations, though, like ~, &, | and
^. Even so,I can't see any way to avoid UB when trying to calculate
the range of int. Equally, I don't have a persuasive argument that it
*can't* be done, either.

--
Ben.

user923005
Guest
Posts: n/a

 03-13-2008
On Mar 12, 5:30*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> Kaz Kylheku <(E-Mail Removed)> writes:
> > On Mar 12, 1:23*pm, (E-Mail Removed) wrote:
> >> On Mar 12, 2:35 pm, Kaz Kylheku <(E-Mail Removed)> wrote:
> >> > 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?

>
> > Unfortunately it is. Shifting a bit into the sign is UB. Only a
> > positive value whose double is representable may be shifted left by
> > one bit.

>
> > This means that the sign bit is quite impervious to bit
> > manipulation.

>
> It must participate in other bit operations, though, like ~, &, | and
> ^. *Even so,I can't see any way to avoid UB when trying to calculate
> the range of int. *Equally, I don't have a persuasive argument that it
> *can't* be done, either.

To compound things, imagine a C implementation where all integral
types were 64 bits (including char).
Even the undefined behavior hacks I posted will fail on those.
In short, I think it is a really difficult problem to solve.
If someone can define a sensible solution, I would be very pleased to
see it.
It might be interesting to see what DMR has to say about it.

Ioannis Vranos
Guest
Posts: n/a

 03-13-2008
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.

C95:

#include <stdio.h>

int main()
{
unsigned x= -1;

int INTMAX=x /2;

int INTMIN= -INTMAX -1;

printf("INTMIN: %d\t", INTMIN);

printf("INTMAX: %d\n", INTMAX);

return 0;
}

Peter Nilsson
Guest
Posts: n/a

 03-13-2008
Ioannis Vranos <(E-Mail Removed)> wrote:
> #include <stdio.h>
>
> int main()
> {
> * * *unsigned x= -1;
> * * *int INTMAX=x /2;

What if UINT_MAX == INT_MAX, or UINT_MAX = 4*INT_MAX+3?

> * * *int INTMIN= -INTMAX -1;

What if INT_MIN == -INT_MAX?

> * * *printf("INTMIN: %d\t", INTMIN);
> * * *printf("INTMAX: %d\n", INTMAX);
> * * *return 0;
> }

--
Peter

Richard Heathfield
Guest
Posts: n/a

 03-13-2008
Peter Nilsson said:

> Ioannis Vranos <(E-Mail Removed)> wrote:
>> #include <stdio.h>
>>
>> int main()
>> {
>> unsigned x= -1;
>> int INTMAX=x /2;

>
> What if UINT_MAX == INT_MAX,

I don't think it can. "For each of the signed integer types, there is a
corresponding (but different) unsigned integer type (designated with the
keyword unsigned) that uses the same amount of storage (including sign
information) and has the same alignment requirements. The range of
nonnegative values of a signed integer type is a subrange of the
corresponding unsigned integer type, and the representation of the same
value in each type is the same." So for UINT_MAX to be == INT_MAX, ints
would need to squeeze twice as many values into the same number of bits as
unsigned ints.

> or UINT_MAX = 4*INT_MAX+3?

See above.

>
>> int INTMIN= -INTMAX -1;

>
> What if INT_MIN == -INT_MAX?

That, however, is a valid objection. For example, INT_MIN might be -32767
rather than -32768.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Ioannis Vranos
Guest
Posts: n/a

 03-13-2008
Richard Heathfield wrote:
> Peter Nilsson said:
>
>> Ioannis Vranos <(E-Mail Removed)> wrote:
>>> #include <stdio.h>
>>>
>>> int main()
>>> {
>>> unsigned x= -1;
>>> int INTMAX=x /2;

>> What if UINT_MAX == INT_MAX,

>
> I don't think it can. "For each of the signed integer types, there is a
> corresponding (but different) unsigned integer type (designated with the
> keyword unsigned) that uses the same amount of storage (including sign
> information) and has the same alignment requirements. The range of
> nonnegative values of a signed integer type is a subrange of the
> corresponding unsigned integer type, and the representation of the same
> value in each type is the same." So for UINT_MAX to be == INT_MAX, ints
> would need to squeeze twice as many values into the same number of bits as
> unsigned ints.
>
>> or UINT_MAX = 4*INT_MAX+3?

>
> See above.
>
>>> int INTMIN= -INTMAX -1;

>> What if INT_MIN == -INT_MAX?

>
> That, however, is a valid objection. For example, INT_MIN might be -32767
> rather than -32768.

C95:

Since sizeof(N)= sizeof(signed N)= sizeof(unsigned N)

where N can be char, short, int, long

and as you mentioned they use the same amount of storage, how can
INT_MIN be equal to INT_MAX since the range of values is the same.