What does this sentence mean?

[Strogian]

I came across this sentence on page 197 of The C Programming Language, 2nd Ed, where it talked about integral conversions. I have no idea what it is supposed to mean. It does go on to explain it in bitwise terms, but this particular sentence just does not make sense to me. Could someone help me understand it?

"Any integer is converted to a given unsigned type by finding the smallest nonnegative value that is congruent to that integer, modulo one more than the largest value that can be represented in the unsigned type."

[Alex Merek]

"Any integer is converted to a given unsigned type by finding the smallest nonnegative value that is congruent to that integer, modulo one more than the largest value that can be represented in the unsigned type."

First of all I think we need to understand what the term congruent means. As per webster: congruent - having the difference divisible by a given modulus (12 is congruent to 2 (modulo 5) since 12-2=2·5).

That explains both congruent and modulo. So in our case, if the largest value that can be represented by the unsigned type is 4 (one less than 5, our modulo) everything works fine and our integer is 2.

hope that helps...

[Strogian]

Actually yes, that does help. I think. :) I actually looked up modulo, and it gave me a slightly different definition, but yours is easier. :)

So lemme think here. We've got a number, say, 5. Now it's being converted to an unsigned integer. Okay, so let's say the max for int is 65536. That means we need a number that is congruent to 5, modulo 65537. Right. The smallest nonnegative integer I can think of would be 65542. 65542-5 = 65537. Well, unless 5 would count, since 5-5=0, and 0 is divisible by anything, right? So it would either be 65537 or 5. 5 seems more logical, but why wouldn't they just say that the number stays the same, then? :)

All right, maybe it's something with negatives. Let's take -5 then. We need a number congruent to -5 (modulo 65537). Okay, now it would have to be 65532, since 65532-(-5)=65537. There's no way to get 0 this time, so that's the one. God, if that's what it's supposed to mean, they sure complicated it up as much as they could. :D

Except that it doesn't really make sense either. I would think that it would either change to the absolute value, or it would change to (32768+5)=32773. So I must be misunderstanding it still.

[Alex Merek]

Okay so our max value is 65536
Our modulo is 65537 (65536+1)
Our integer is 5.

Let the number congruent to 5 modulo 65537 be X. Thus based on definition above: X - 5 == 5 * 65537. Thus X == 327,690. Thats our congruent number. I dont know if thats the smallest, but it sure is nonnegative :D

[bwkaz]

The maximum value for an unsigned short int is never 65536. The maximum value for an unsigned short int is 65535.

So the modulo is 65536.

X - 5 = y * 65536

X is the number we'll have, and y is any integer (if y wasn't integral, then X-5 wouldn't be evenly divisible by 65536).

We need to choose a y such that X is minimized (but not less than 0). So rearrange the equation:

X = 65536 * y + 5

Normally, you'd take the derivative of X WRT y and set it equal to zero to find the minimum, but the derivative is 65536 (a constant), so it's never 0.

What we have to do here is realize that the equation above is a set of points that lie on a line (with a really big positive slope), then we can say that the minimum X value is when y is 0 (X is 5, and this point was found by inspection of the graph, in the first quadrant only). Since this X is nonnegative, it's our answer.

Casting 5 to an unsigned short int results in 5.