Signed mod unsigned

[Johannes Bauer]

Hi group,

today I ran into something I honestly did not expect. Consider this snippet:

#include <stdio.h>

int main() {
int i1, i2;
unsigned int u2;

i1 = -1;

i2 = 30;
u2 = 30;

printf("%d\n", i1 % i2);
printf("%d\n", i1 % u2);
return 0;
}

I expected to find the output "-1 / -1". Instead the result I got was
"-1 / 15". Apparently when getting the remainder of a signed by a
unsigned int, the signed is silently promoted to unsigned in twos
complement and then the operation is performed, i.e.

0xffffffff % 30 == 15

I would have expected at least a warning since I find this highly
unintuitive -- my expectation would be that the unsigned becomes a
(truncated) signed and a warning. Instead gcc does not emit a warning
(-Wall -Wextra) and silently performs above operation.

Is this really in accordance with the C standard or is gcc doing
something weird here?

Best regards,
Joe

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[James Kuyper]

Hi group,

today I ran into something I honestly did not expect. Consider this snippet:

#include <stdio.h>

int main() {
int i1, i2;
unsigned int u2;

i1 = -1;

i2 = 30;
u2 = 30;

printf("%d\n", i1 % i2);
printf("%d\n", i1 % u2);
return 0;
}

I expected to find the output "-1 / -1". Instead the result I got was
"-1 / 15". Apparently when getting the remainder of a signed by a
unsigned int, the signed is silently promoted to unsigned in twos
complement and then the operation is performed, i.e.

0xffffffff % 30 == 15

I would have expected at least a warning since I find this highly
unintuitive -- my expectation would be that the unsigned becomes a
(truncated) signed and a warning. Instead gcc does not emit a warning
(-Wall -Wextra) and silently performs above operation.

Is this really in accordance with the C standard or is gcc doing
something weird here?

In most binary expressions (modulus expressions are no exception -
6.5.5p3), the operands are subject to what is called the usual
arithmetic conversions (6.3.1.8) before the operation is performed.
Those conversions include the integer promotions, which leave both
operands unchanged in this case. The relevant rule is that when one
promoted type is unsigned, and the other is signed, if the unsigned type
has an integer conversion rank greater than or equal to that of the
signed type, then the operand of the signed type is converted to the
unsigned type. "unsigned int" is required to have the same integer
conversion rank as "int" (6.3.1.1p1);

So the behavior you describe is not only allowed, but required, by the C
standard. There's some minor details about your description that should
be modified: this is not an example of what the C standard calls a
promotion, and it has nothing to do with 2's complement. The C standard
also allows 1's complement and sign-magnitude representations
(6.2.6.2p2), and the conversion from a signed value to an unsigned type
follows the same rules regardless of the representation used for the
signed type. A value 1 greater than the maximum value representable in
the unsigned type is either repeatedly added to, or repeatedly subtract
from, the value until the result is representable in the unsigned type
(6.3.1.3p2).

The machine instructions needed to obtain this result can be quite
different, depending upon which representation is used for the signed
type. However, the result of the conversion should be exactly the same
for all three representations, it depends only upon the initial value
represented and maximum representable value of the unsigned type.

 

[gwowen]

Is this really in accordance with the C standard or is gcc doing
something weird here?

James has given a complete technical answer, so I won't add to that.
What I will say is that there's no universally accepted definition of
what remainder/modulus means, so whatever intuition tells you[0],
someone is going to consider it to be wrong.

When it comes to remainders involving negatives, intuition is
worthless.

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

 

[Edward Rutherford]

Hi group,

today I ran into something I honestly did not expect. Consider this
snippet:

#include <stdio.h>

int main() {
int i1, i2;
unsigned int u2;

i1 = -1;

i2 = 30;
u2 = 30;

printf("%d\n", i1 % i2);
printf("%d\n", i1 % u2);
return 0;
}

I expected to find the output "-1 / -1". Instead the result I got was
"-1 / 15". Apparently when getting the remainder of a signed by a
unsigned int, the signed is silently promoted to unsigned in twos
complement and then the operation is performed, i.e.

0xffffffff % 30 == 15

I would have expected at least a warning since I find this highly
unintuitive -- my expectation would be that the unsigned becomes a
(truncated) signed and a warning. Instead gcc does not emit a warning
(-Wall -Wextra) and silently performs above operation.

Is this really in accordance with the C standard or is gcc doing
something weird here?

This looks like a compiler bug. I would report it to a Gcc mailing list.

 

[James Kuyper]

This looks like a compiler bug. I would report it to a Gcc mailing list.

I explained in my response why I believe that this behavior is not
merely allowed, but mandated, by the C standard. Do you disagree? If so,
on what grounds?

 

[Johannes Bauer]

On 06.06.2012 16:41, James Kuyper wrote:

[...]

So the behavior you describe is not only allowed, but required, by the C
standard.

James, thank you very much for the verbose and detailed explanation. In
15 years of C programming, I did not run into that caveat

Best regards,
Johannes

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[Johannes Bauer]

When it comes to remainders involving negatives, intuition is
worthless.

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

Best regards,
Joe

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[James Kuyper]

On 06.06.2012 16:41, James Kuyper wrote:

[...]

So the behavior you describe is not only allowed, but required, by the C
standard.

James, thank you very much for the verbose and detailed explanation. In
15 years of C programming, I did not run into that caveat

This issue comes up in almost every binary operation involving negative
values and unsigned integers of a type with equal or greater integer
conversion rank; if you've not noticed it before in 15 years of C
programming, then you've probably been deliberately avoiding mixing
negative values with unsigned types - which is generally a good idea.

 

[BartC]

On 06.06.2012 16:53, gwowen wrote:

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1, 15 and 29; any other possible results for the same expression?

 

[Johannes Bauer]

if you've not noticed it before in 15 years of C
programming, then you've probably been deliberately avoiding mixing
negative values with unsigned types - which is generally a good idea.

I try to do arithmetic, indexing and counting (i.e. loop variables) with
signed types and use unsigned almost always only for bit operations (or
where the well-defined overflow is needed). Has worked well so far

Best regards,
Joe

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[Johannes Bauer]

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1, 15 and 29; any other possible results for the same expression?

If I understand James' post correct, in the expression -1 % 30u the "-1"
is converted to UNSIGNED_MAX (which happens to be (2^32)-1 on my system).

Since int IIRC is only required to have >= 16 bits, one could image a
n-bit system in which the expression would evaluate to something
different. In particular, if bits % 4 == 0, it evaluates to 15. For

bits % 4 result
0 15
1 1
2 3
3 7

So I think the expression can be either -1, 15, 29, 1, 3 or 7 depending
on the language and platform

Best regards,
Johannes

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[Eric Sosman]

On 06.06.2012 16:53, gwowen wrote:

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1%30u in C *can be* 15.

-1, 15 and 29; any other possible results for the same expression?

In C, the possible results are 1, 3, 7, 15.

 

[Ben Bacarisse]

On 06.06.2012 16:53, gwowen wrote:

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1%30u in C *can be* 15.

-1, 15 and 29; any other possible results for the same expression?

In C, the possible results are 1, 3, 7, 15.

I think -1 is also possible on those awkward systems where UINT_MAX ==
INT_MAX.

 

[Edward Rutherford]

I explained in my response why I believe that this behavior is not
merely allowed, but mandated, by the C standard. Do you disagree? If so,
on what grounds?

This outcome just seems counterintuitive to me. Even if it is permitted
by the C standard, this option is kinda retarded and I'd say the compiler
has poor quality of implementation.

Best regards,
E.P.R.

 

[James Kuyper]

This outcome just seems counterintuitive to me. Even if it is permitted
by the C standard, this option is kinda retarded and I'd say the compiler
has poor quality of implementation.

It's not merely permitted; it's not an option; it's required. The phrase
"Quality of implementation" is normally considered to apply only to
issues where the standard gives a conforming implementation freedom to
choose how something is done. The only freedom that the implementation
has that's relevant to this program is in number of value bits in an
unsigned int. You're not suggesting, I hope, that choosing 32 for that
number gives the implementation a low QoI? It's a pretty popular choice.

 

[Eric Sosman]

On 06.06.2012 16:53, gwowen wrote:

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1%30u in C *can be* 15.

-1, 15 and 29; any other possible results for the same expression?

In C, the possible results are 1, 3, 7, 15.

I think -1 is also possible on those awkward systems where UINT_MAX ==
INT_MAX.

Quite right; thanks for correcting my oversight.

 

[Tim Rentsch]

On 06.06.2012 16:53, gwowen wrote:

[0] My intuition, for example, tells me that -1 % 30 equals 29. My
intuition is worthless too.

Well, it's always nice when intuition at least overlaps with the reality
of compilers or interpreters

BTW, -1 % 30 == 29 in Python. I did know that C did not give up the
sign, but I'd have expected for example -100 % 30 == -10 (it is 20 in
Python). Anyways, it does so for signed/signed types, so I'm going to
use these.

So -1%30 is -1 in C and 29 in Python. While -1%30u in C is 15.

-1%30u in C *can be* 15.

-1, 15 and 29; any other possible results for the same expression?

In C, the possible results are 1, 3, 7, 15.

I think -1 is also possible on those awkward systems where UINT_MAX ==
INT_MAX.

Sort of. This curious behavior was not present in C90 or
in the original C99. It was added via a TC (it appears
in N1124) as a result of Defect Report 230. However,
subsequently it was acknowledged that the strange effect
on the promotion rules was an unintended consequence of a
poor wording choice to address the DR. This has since
been corrected in C11 -- under C11 unsigned int is never
'promoted' to int even if UINT_MAX == INT_MAX. Hence the
expression -1%30u can never be -1 (or any negative number)
under the current standard.

 

[Johannes Bauer]

Sort of. This curious behavior was not present in C90 or
in the original C99. It was added via a TC (it appears
in N1124) as a result of Defect Report 230. However,
subsequently it was acknowledged that the strange effect
on the promotion rules was an unintended consequence of a
poor wording choice to address the DR. This has since
been corrected in C11 -- under C11 unsigned int is never
'promoted' to int even if UINT_MAX == INT_MAX. Hence the
expression -1%30u can never be -1 (or any negative number)
under the current standard.

Wow -- I really don't feel bad about tripping over this now. It *is*
indeed confusion and without a *lot* of insight into the standard it is
quite hard to tell what the expression will evaluate to on different
platforms.

Best regards,
Joe

--

Zumindest nicht öffentlich!

Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <[email protected]>

 

[Ben Bacarisse]

Sort of. This curious behavior was not present in C90 or
in the original C99. It was added via a TC (it appears
in N1124) as a result of Defect Report 230. However,
subsequently it was acknowledged that the strange effect
on the promotion rules was an unintended consequence of a
poor wording choice to address the DR. This has since
been corrected in C11 -- under C11 unsigned int is never
'promoted' to int even if UINT_MAX == INT_MAX. Hence the
expression -1%30u can never be -1 (or any negative number)
under the current standard.

Well that's pleasing to know, although I've never had to wrestle with
such an implementation. As far as I can tell, if it followed C99 to the
letter, the only way to do unsigned arithmetic would be to force one or
more of the operands to be "wider" than unsigned int. I put wider in
quotes because I think you can do it even if there no type that is
actually wider because of the way conversion rank is defined. Thus
-1%30ul can't be -1 even on the most literal C99 implementation.

Still, it's good that this has been tidied up. It will save much
nit-picking time here. I wonder if it will have any other effect on the
world.

 

[Ben Bacarisse]

Wow -- I really don't feel bad about tripping over this now. It *is*
indeed confusion and without a *lot* of insight into the standard it is
quite hard to tell what the expression will evaluate to on different
platforms.

I don't want to make you feel bad again, but this last case is one of
the oddest corners of C and can be quite safely ignored by almost
everyone (indeed by everyone, soon, if C11 gets a hold).

The main fact, that mixed int and unsigned int arithmetic is done by
converting the int operand to unsigned int, is commonplace and needs to
be kept in mind for those times when it will matter. The fact that it's
happening is often masked by implementations that use 2's complement and
define the unsigned to int conversion as simply "stuffing the bits back
in there". However

int x;
/* ... */
x = x + 1u;

can raise a signal when x is, say, -1 on systems that define the
conversion of out-of-range values to int as doing so. On most systems
it "just works" as if 1 had been used in place of 1u. Real examples are
often more disguised since you might be adding a size_t value to x.

The fact that -1 % 30u can have different values on different systems is
just a reflection of the fact that UINT_MAX can have different values
depending on the number of bits used by unsigned int.

So, once again, my intent is not to make you feel you should have known
all this, but simply to say that it is *worth* knowing, and that it's
not actually as complicated as this thread seems to suggest.