Why does the modulo operator result in negative values? [duplicate]

Question

Why do such operations:

std::cout << (-7 % 3) << std::endl;
std::cout << (7 % -3) << std::endl;

give different results?

-1
1

Carve

Answer 1

From ISO14882:2011(e) 5.6-4:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined. For integral operands the / operator yields the algebraic quotient with any fractional part discarded; if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

The rest is basic math:

(-7 / 3) => -2
-2 * 3   => -6
so a % b => -1

(7 / -3) => -2
-2 * -3  => 6
so a % b => 1

Note that

If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

from ISO14882:2003(e) is no longer present in ISO14882:2011(e)

Credendum

The expression "algebraic quotient" isn't present in ISO 14882:2003; the expression there is just "quotient" (and what is implementation defined is whether -7/3 results in -2 or -3). – Keeley

@JamesKanze: Note that the quote is from the current standard, I will try to emphasize it in the answer. – Credendum

I think no matter which way and how many times you skin that cat, the fundamental fact is that divide and modulo with signed operands is implementation defined. There's always a "which way" choice in some guise or another. The guaranteed identity at the end of that quote is what's important. (Though I think C99 may actually fix that choice.) – Adrienneadrift

It looked like you were quoting something, but what you quote doesn't correspond to either of the versions I have handy. My version of C++ 2003 is in fact a very late draft, so the wording my have may have changed slightly---if you're quoting the official C++ 2003, then it did. The change was made in C in C99, so the definitive version of C++03 might reflect it (or partially reflect it). – Keeley

@JamesKanze: C++03 still contains the implementation definedness, it is C++11 which removes it. (and requires divisions to follow fortran, basically) – Credendum

Great answer, I didn't realize this issue with % in the case of negative arguments. – Liberalism

@KerrekSB It is defined now in C++11. – Linzer

@Buge: C++11 is based on C99, so that makes sense. – Adrienneadrift

Answer 2

a % b

in c++ default:

(-7 / 3) => -2
-2 * 3   => -6
so a % b => -1

(7 / -3) => -2
-2 * -3  => 6
so a % b => 1

in python:

-7 % 3 => 2
7 % -3 => -2

in c++ to python:

(b + (a % b)) % b

Pliner

There is no "C++ default" regarding the resulting sign in case of negative numbers. – Romany

Answer 3

The sign in such cases (i.e when one or both operands are negative) is implementation-defined. The spec says in §5.6/4 (C++03),

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

That is all the language has to say, as far as C++03 is concerned.

Ladd

That's all the language had to say. C++11 (like C99) adopts the Fortran rules of rounding to zero (i.e. dropping the fractional part). In practice, all hardware had adopted the Fortran rules long ago, so all all implementations already did it this way anyway. (The purpose of the "implementation-defined" is to allow C/C++ to do whatever the hardware does. I think some very old hardware did always round down, so that -7/3 would result in -3, but that would be in a very distant past.) – Keeley

@JamesKanze: If b is a power of 2, it used to be possible to compute n % b as n & (b-1). The new standard requires that it be computed as n < 0 ? n | -b : n & (b-1). Likewise, n / b cannot be written as a simple shift, even on hardware that supports arithmetic shifts; instead, on such systems, an expression like n/16 (if n is an int32) must be written as n < 0 ? (n+15) >> 4 : n >> 4. Horrible standard, IMHO. Note that since non-power-of-two division is inherently slow anyway, mandating Euclidian behavior wouldn't have slowed it down much. – Rainie

@Rainie An expression like n / 16 should be written as n / 16. Say what you mean. The newly mandated behavior is the behavior people expect (whether it is right or wrong), and the behavior of all existing hardware. – Keeley

@JamesKanze: It is NOT the behavior of existing hardware in the case of optimizing divide-by-power-of-two operations as shifts. Under the old rules, foo /= 16 could be written as asr [dword foo],4. Under the new rules, the optimal representation requires many more instructions [perhaps mov eax,[foo] / mov ebx,eax, asr eax,31 / lsr eax,28 / add eax,ebx / asr eax,4 / mov [foo],eax] Not as slow as a divide instruction, but a lot more work than a simple shift. – Rainie

@Rainie Complaining about the way that an arithmetic function in a human readable language works because of how many instructions have to be done in machine code to keep it consistent instead of using a hacky shortcut that only simplifies operations with a tiny subset of all possible values? Wow. Just wow. slow clap – Countryside

@CptRobby: I've encountered a lot of places where I've wanted Euclidian or rounded division. Truncated division, not so much; in the only place I recall I could have benefited from it was a performance-critical piece of code where I manually adjusted the result of a shift-right operation because the compiler's implemented signed n/2 using a general-purpose division routine. – Rainie

@Rainie Not trying to be a jerk here, but I think it's important to remember that math is actually important outside of the inner workings of a CPU. If a math teacher asks you what -5/2 is, they would definitely accept -2.5 or -2½, but I doubt they would accept -(3-½) or -3+½ (I can't even figure out how you would write it, it's such a non-standard way of thinking). – Countryside

@Rainie Also, am I correct in my assumption that this method of bit shifting would only work for divisors that are a power of 2 and all other numbers would require the longer approach, in which case computational difficulty is equivalent regardless of whether the result is rounded to zero or negative infinity? – Countryside

@CptRobby: Would the math teacher accept "-2.-5?" as an answer? Or accept that 13/4 is -3.-2-5? Human-readable base conversion requires that one handle negative values before one starts, or constantly throughout; using floored division doesn't help. On the other hand, if the teacher asked for N/3 rounded to the nearest integer, using Euclidian division one could compute (N+1)/3 without regard for whether N was positive or negative. When using truncated division, one needs to handle positive and negative numbers separately. – Rainie

@Rainie What are you talking about? When I was taught math, I learned to IGNORE the negative sign when doing division until the very end. So for -N/3, you just calculate N/3 and at the end you add the negative sign to the answer. I don't think we're even talking the same language here or something because I don't see how anything you just said relates to anything I said (or reality). I do not want the comment section of SO to become like the comment section of YouTube. So I will just wish you well and move on. Thanks. :) – Countryside

@CptRobby: In "human" language, -7/4 may be written as -1¾, but in C, -7%4 yields -3, not +3, so code is going to have to do something to make the fraction come out right; the only sane way that will work with e.g. -3/4 is to output a minus, flip the sign of the fraction, and proceed from there, at which point handling of a negative dividend would be irrelevant. The only use I've ever found for a negative remainder was as a means of determining that the result of a division needed to be adjusted. Are there other uses? – Rainie

@Rainie You're talking about formatting a string to show a fraction like "-7 ÷ 4 = -1 3/4"? Easy. I'm going to switch to C# to do it though since I've not done anything in C++ for more than a decade. int x = -7, y = 4; string.Format("{0} ÷ {1} = {2}{3}", x, y, x/y, (x%y==0) ? "" : string.Format(" {0}/{1}", Math.Abs(x%y), Math.Abs(y))); That handles every possible value of x and y in 2 lines of code. However, I don't see how this is really relevant since trying to do this with Euclidean division, you would end up with "-7 ÷ 4 = -2 1/4" and trying to fix it would be much more complicated. – Countryside

@CptRobby: Given Euclidian, floored, or truncated division, one simply starts by printing a minus sign and flipping the sign of the value if it was negative, which often ends up being necessary when using truncated division if one e.g. wants a rounded result. – Rainie

@Countryside You seem to forget that the entire design philosophy of C revolves around hacky shortcuts to produce faster assembly code. – Disaffect