Unexpected modulo behavior with long integers

Question

The modulo % operator of C++ behaves strangely when operands are (un)signed or long.

Why would mod(signed int, unsigned int) and mod(signed long long int, unsigned long long int) produce different results? How do I do if I want the correct one (here: 11183)?

Note: If I follow my algorithm, I should call uint64_t mod(int64_t, uint64_t).

// Tip: 11183 is the "correct" expected result.

(                   int)(-3365) % (                   int)(15156) = -3365
(  signed           int)(-3365) % (  signed           int)(15156) = -3365
(unsigned           int)(-3365) % (unsigned           int)(15156) = 11183
(  signed           int)(-3365) % (unsigned           int)(15156) = 11183
(unsigned           int)(-3365) % (  signed           int)(15156) = 11183

(              long int)(-3365) % (              long int)(15156) = -3365
(  signed      long int)(-3365) % (  signed      long int)(15156) = -3365
(unsigned      long int)(-3365) % (unsigned      long int)(15156) = 2555
(  signed      long int)(-3365) % (unsigned      long int)(15156) = 2555
(unsigned      long int)(-3365) % (  signed      long int)(15156) = 2555

(         long long int)(-3365) % (         long long int)(15156) = -3365
(  signed long long int)(-3365) % (  signed long long int)(15156) = -3365
(unsigned long long int)(-3365) % (unsigned long long int)(15156) = 2555
(  signed long long int)(-3365) % (unsigned long long int)(15156) = 2555
(unsigned long long int)(-3365) % (  signed long long int)(15156) = 2555

(          int_fast16_t)(-3365) % (          int_fast16_t)(15156) = -3365
(         uint_fast16_t)(-3365) % (          int_fast16_t)(15156) = 2555
(          int_fast16_t)(-3365) % (         uint_fast16_t)(15156) = 2555
(         uint_fast16_t)(-3365) % (         uint_fast16_t)(15156) = 2555

(          int_fast32_t)(-3365) % (          int_fast32_t)(15156) = -3365
(         uint_fast32_t)(-3365) % (          int_fast32_t)(15156) = 2555
(          int_fast32_t)(-3365) % (         uint_fast32_t)(15156) = 2555
(         uint_fast32_t)(-3365) % (         uint_fast32_t)(15156) = 2555

(          int_fast64_t)(-3365) % (          int_fast64_t)(15156) = -3365
(         uint_fast64_t)(-3365) % (          int_fast64_t)(15156) = 2555
(          int_fast64_t)(-3365) % (         uint_fast64_t)(15156) = 2555
(         uint_fast64_t)(-3365) % (         uint_fast64_t)(15156) = 2555

PS: More information about my system:

Linux pc-gi-446 4.4.0-36-generic #55-Ubuntu SMP x86_64 x86_64 x86_64 GNU/Linux
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609

Why don't you investigate what is the value of `(uint64_t) -3365`? Let's call it `val`; then are you still surprised what happens when you calculate `val % 15156`? — Kaz, Apr 28 '17 at 18:41
Unsigned types do not represent negative values. When a negative integer is converted to an unsigned type, a modulo operation happens to produce a non-negative value in the range of that unsigned type. When you then apply your own modulo, that's a second modulo on top of that one. The modulo operation which is applied to the original value uses a modulus of `(1 + MAX)` where `MAX` is the highest value of that unsigned type. For instance `(unsigned int) -3` causes the `-3` to be reduced to the smallest positive value modulo `ULONG_MAX` + 1, resulting in the value `ULONG_MAX - 2`. — Kaz, Apr 28 '17 at 18:45

Stephan Lechner · Answer 1 · 2017-04-28T18:53:23.623

1

Try

unsigned int x = -3365; printf("%u", x);

It won't print "3365", but will print the max value of an unsigned int minus 3365 + 1, i.e. UINT_MAX-3365+1, which is 4294963931.

So (unsigned int)(-3365) % (unsigned int)(15156) is the same as unsigned int z = 4294963931 % 15156; printf("%u\n", z) and gives 11183.

edited Apr 28 '17 at 18:53

answered Apr 28 '17 at 18:44

Stephan Lechner

34,891
4
35
58

score 1 · Answer 2 · edited May 23 '17 at 11:46

1

% is not modulo.

See also What's the difference between “mod” and “remainder”?, a C answer that applies here too.

In C++, % is the remainder of a division. -3365/15156 --> 0. The remainder of the division is -3365.

(int)(-3365) % (int)(15156) = -3365

The following appears wrong at first, yet due to conversion to unsigned math, it is correct

(unsigned long int)(-3365) % (unsigned long int)(15156) = 2555
(ULONG_MAX + 1 -3365) % 15156 = 2555

edited May 23 '17 at 11:46

Community

1
1

answered Apr 28 '17 at 20:16

chux - Reinstate Monica

143,097
13
135
256

Why would mod(signed int, unsigned int) and mod(signed long long int, unsigned long long int) produce different results? – Apr 29 '17 at 08:52
1

@Odepax Step 1: With `signed int % unsigned int` both arguments are converted to `unsigned` before the `%` occurs. With `signed long long % unsigned long long` both arguments are converted to `unsigned long long` before the `%` occurs. Is there any question of why that happens? Step 2: what values are those first arguments changed to? – chux - Reinstate Monica Apr 30 '17 at 19:31

Unexpected modulo behavior with long integers

2 Answers2

Linked