Programming Puzzle

[Joona I Palaste]

JKop <[email protected]> scribbled the following

Gordon Burditt posted:

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

The overflow of unsigned integer types is perfectly defined in ISO
standard C. The values "roll over", which means that if a value is
larger than the maximum, the maximum is substracted from it. For
example suppose a 16-bit unsigned short. Attempting to store 65536
into it will store 0, attempting to store 65537 will store 1, and so
on.
The overflow of *signed* integer types is not defined.

 

[Joona I Palaste]

Joona I Palaste <[email protected]> scribbled the following

JKop <[email protected]> scribbled the following

The overflow of unsigned integer types is perfectly defined in ISO
standard C. The values "roll over", which means that if a value is
larger than the maximum, the maximum is substracted from it. For
example suppose a 16-bit unsigned short. Attempting to store 65536
into it will store 0, attempting to store 65537 will store 1, and so
on.
The overflow of *signed* integer types is not defined.

Dang, made a fencepost error. I meant, if a value is larger than the
maximum value, the *number of possible values* is substracted from it.
As the minimum value is 0, the number of possible values is equal to
the maximum value plus one.

 

[Peter Nilsson]

Gordon Burditt posted:


This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

C99 states... [C90 and C++ are not dissimilar...]

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Although, there is slight catch. For unsigned types promotable to int, there are potential
problems...

unsigned short x = 1024;
unsigned short y = 1024;
unsigned short z = x * y;

The unsigned short operands of * will likely be promoted to int, and the calculation 1024
* 1024 can overflow a 16-bit int.

 

[Richard Herring]

You'll get a warning saying main() has no return value.

Not on this side of the crossposting ;-)

 

[Richard Herring]

Given an array (group) of numbers write all the possible sub groups of
this group.

Beware that this can't be using "group" in its normal mathematical
sense, since it doesn't specify an operator. If it really does mean
group, you need to remember that not every subset constitutes a
subgroup.

 

[Ioannis Vranos]

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).






Regards,

Ioannis Vranos

 

[JKop]

Ioannis Vranos posted:

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".


Consider (on an 8-Bit char system):


unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );


I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.


Let's try swap the values of a and b without a temp variable:


int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b; // a == 300, b == 100

b = a - b; // a == 300, b == 200

a = a - b; // a == 100, b == 200

}


That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}


Now, as far as I know, if you switch

a == 200, b == 100


you don't get:

a == 100, b == 100


But that's just human observation.


-JKop

 

[Walter Tross]

JKop 2004-06-28 :

Ioannis Vranos posted:



Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".


Consider (on an 8-Bit char system):


unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );


I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.


Let's try swap the values of a and b without a temp variable:


int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b; // a == 300, b == 100

b = a - b; // a == 300, b == 200

a = a - b; // a == 100, b == 200

}


That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}


Now, as far as I know, if you switch

a == 200, b == 100


you don't get:

a == 100, b == 100


But that's just human observation.

Jkop, you didn't observe anything.
I must tell you: you forgot to switch on your brain before writing,
as usual. Please don't fill this newsgroup with useless, wrong and
misleading posts.

Walter Tross

 

[Richard Herring]

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".


Consider (on an 8-Bit char system):


unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );


I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.[/QUOTE]

So it takes the result mod 256. That's 44.

Let's try swap the values of a and b without a temp variable:


int main()
{
unsigned char a = 200;
unsigned char b = 100;
a = a + b; // a == 300, b == 100
b = a - b; // a == 300, b == 200
a = a - b; // a == 100, b == 200
}


That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;
unsigned char b = 100;
a = a + b // a == 45, b == 100

Bzzzt. Out by 1. Overflow, so subtract 256. a == 44, b == 100

b = a - b // a == 200, b == 100

What? a doesn't change. b underflows, so add 256. a = 44, b == 200

a = a - b // a == 100, b == 100

a underflows, so add 256. a == 100, b == 200

}

Modulo 256, the two "programs" are identical.

Now, as far as I know, if you switch

a == 200, b == 100


you don't get:

a == 100, b == 100


But that's just human observation.

My observation would be "when in hole, stop digging."

 

[John Cochran]

Ioannis Vranos posted:


SNIP

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}

You need to check your math. You have
made a mistake. Here is what really happens...

bash-2.05b$ cat demo.c
#include <stdio.h>

int main()
{
unsigned char a = 200;
unsigned char b = 100;

printf("1. %u %u\n", a, b);
a = a + b;
printf("2. %u %u\n", a, b);
b = a - b;
printf("3. %u %u\n", a, b);
a = a - b;
printf("4. %u %u\n", a, b);

return 0;
}

bash-2.05b$ make demo
cc -O -pipe -march=pentium3 demo.c -o demo
bash-2.05b$ ./demo
1. 200 100
2. 44 100
3. 44 200
4. 100 200
bash-2.05b$

 

[Richard Delorme]

JKop a écrit :

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

should be:
a = a + b; // a == 44, b == 100

b = a - b // a == 200, b == 100

should be:
b = a - b; // a == 44, b == 200

a = a - b // a == 100, b == 100

should be:
a = a - b; // a == 100, b == 200

}


Now, as far as I know, if you switch

a == 200, b == 100


you don't get:

a == 100, b == 100

No, you get a == 100, b == 200.

But that's just human observation.

^^^^^

hmmm... next time use a computer.

 

[JKop]

John Cochran posted:

1. 200 100
2. 44 100
3. 44 200
4. 100 200

I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

-JKop

 

[John Cochran]

John Cochran posted:



I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

-JKop

Overflow and underflow for unsigned integers is very well defined in C and C++,
that's what people have been attempting to tell you in this thread for quite
some time.

 

[Ioannis Vranos]

John Cochran posted:





I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

For *unsigned integers*, the behaviour is well-defined both for overflow
and underflow (it wraps around). So you can get the maximum value of an
unsigned integer by using -1. This one is used *extensively*.



For example:


// Equivalent to unsigned long li=numeric_limits<unsigned long>::max();
unsigned long li=-1;


unsigned char uc=-1;

and so on.






Regards,

Ioannis Vranos

 

[Dan Pop]

You'll get a warning saying main() has no return value.

Chapter and verse, please.

Dan

 

[jive]

Explain to me how *two* variables can share the same memory address.

int &value, another;
value = another = 9;
value^another = ??;

jive

 

[Dan Pop]

JKop <[email protected]> scribbled the following

The only foolish assumption is that bits behave like water...

It *can* be done! Not with all kinds of variables, but with unsigned
integer types, it's easy.

If you can do it with unsigned integer types, you can do it with all kinds
of objects, by aliasing them with arrays of unsigned char.

Not one, but *two* ways to do it have been
shown in this thread. Of course it will break down if those variables
happen to share the same memory location, which can be the case if using
pointers and indirecting through them.

OTOH, if you're using pointers, there's nothing preventing you from
testing the pointers for equality, before starting, is there?

So, the method can be universally used in C, if there is a *good* reason.
And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some
systems can have smaller memories than others...).

Dan

 

[Dan Pop]

I had somewhere in my mind the unsigned restriction, but then I checked
the standard and saw that XOR is safe to be applied on both integral
types and enumerations. Then how does this unsigned restriction come?

C99 answer:

4 Some operators (the unary operator ~, and the binary operators
<<, >>, &, ^, and |, collectively described as bitwise
operators) are required to have operands that have integer
type. These operators return values that depend on the internal
representations of integers, and have implementation-defined
and undefined aspects for signed types.

Consider, for example, 0 ^ 0, whose result (an int with all bits set) is
a trap representation, as explicitly allowed by C99 for one's complement.

It's hard to find an example for two's complement using the ^ operator,
but it can be done with ~INT_MAX, if the representation with the sign
bit set and all the value bits reset is a trap representation (again,
explicitly allowed by C99 for two's complement and sign-magnitude).

Whether real world implementations have such trap representations is a
completely different story...

Dan

 

[Howard]

Ooops.. return !(x | 0x0001);

Also not correct. That sets bit 1, which still gives you false as the final
result.

I think what you meant was "return !(x & 0x0001);". That test tells you if
bit 1 is set, which is true for any odd number. But, even that test only
checks if it's even (i.e., k*(2^1)) for some integer value k). The question
asks if it's a power of 2, which means 2^n for some integer value n.

A [positive] integer which is exactly a power of two has one and only one
bit set. (i.e., 0001=2^0, 0010=2^1, 0100=2^2, 1000=2^3, for a 4-bit
integer) So you need to loop through the bits, counting how many are set,
and it there is only one bit set, then it's a power of two. (And, you need
to know the size of the integer in bits first, as well as whether negative
numbers are allowed, in which case you also need to know how those are
represented in your system).

-Howard