13

Possible Duplicate:
C++ operator % guarantees

In c++ 98/03

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; 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.

In c++ 11:

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;81 if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

As you can see the implementation-defined for the sign bit is missing, what happens to it ?

Community
  • 1
  • 1
RoundPi
  • 5,819
  • 7
  • 49
  • 75
  • What are you trying to do? And how this comes as a obstacle for that? – AnandVeeramani Oct 27 '12 at 13:49
  • 1
    @AnandVeeramani: some people just want to avoid undefined (or, in this case, implementation-defined) behavior. I'm glad he asked this, I have avoided modulo when the values could have been negative. – moswald Oct 27 '12 at 14:01
  • 1
    Also, see: http://stackoverflow.com/q/3609572/485561 – Mankarse Oct 27 '12 at 14:03
  • 1
    C++ 98/03 also had this footnote: "According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero" C++11 simply made that a requirement of the standard (as C99 did for C). Removing the implementation defined part of the `%` operator is a consequence of that. – Michael Burr Oct 27 '12 at 15:21
  • @moswald: you would have to avoid using `/` operator in those cases as well, since it is similarly implementation defined. – Michael Burr Oct 27 '12 at 15:29
  • @MichaelBurr: In C++ 11 & C99 it's standard defined ? – RoundPi Oct 27 '12 at 15:32
  • @Gob00st: as mentioned in the answers, the behavior of the `/` operator for integral operands in C++11 is required to truncate toward zero. That is also true in C99. Prior standards left it implementation defined. Note that the `div()` function (and relatives) have always been specified to truncate toward zero. – Michael Burr Oct 27 '12 at 16:15
  • Truncation towards zero was the *de facto* standard in C89 implementations; all C99 did was codify it. – dan04 Oct 27 '12 at 16:39
  • A good [Wikipedia page](http://en.wikipedia.org/wiki/Modulo_operation) on the topic. – Luc Danton Oct 27 '12 at 20:31

2 Answers2

22

The behaviour of % was tightened in C++11, and is now fully specified (apart from division by 0).

The combination of truncation towards zero and the identity (a/b)*b + a%b == a implies that a%b is always positive for positive a and negative for negative a.

The mathematical reason for this is as follows:

Let ÷ be mathematical division, and / be C++ division.

For any a and b, we have a÷b = a/b + f (where f is the fractional part), and from the standard, we also have (a/b)*b + a%b == a.

a/b is known to truncate towards 0, so we know that the fractional part will always be positive if a÷b is positive, and negative is a÷b is negative:

sign(f) == sign(a)*sign(b)

a÷b = a/b + f can be rearranged to give a/b = a÷b - f. a can be expanded as (a÷b)*b:

(a/b)*b + a%b == a => (a÷b - f)*b+a%b == (a÷b)*b.

Now the left hand side can also be expanded:

(a÷b)*b - f*b + a%b == (a÷b)*b

a%b == f*b

Recall from earlier that sign(f)==sign(a)*sign(b), so:

sign(a%b) == sign(f*b) == sign(a)*sign(b)*sign(b) == sign(a)

Mankarse
  • 39,818
  • 11
  • 97
  • 141
  • @mata: The sign is only determined by `a`, you have messed up the arithmetic there (-1/2) = -0.5 = 0 (after truncation), so 0 + x = -1, so x = -1. – Mankarse Oct 27 '12 at 14:26
  • @Mankarse:The equation is always there (as in 03 standard), the only thing new seems to be what's so called 'truncation towards zero'. What this 'truncation towards zero' all about ? – RoundPi Oct 27 '12 at 14:26
  • 1
    @Gob00st: Truncation towards zero means that the fractional part of the result of a division is discarded in the result, so 5/4 == 1.25 => 1 (discard 0.25), and -7/4 == -1.75 => -1 (discard -0.75). – Mankarse Oct 27 '12 at 14:28
  • Yes that's always there isn't it ? What I meant was how's this implies "that a%b is always positive for positive a and negative for negative a." ? Whereas in 03 standard is not. – RoundPi Oct 27 '12 at 14:31
  • @Gob00st: See my edit, in C++03, we could not be sure that `sign(f)==sign(a)*sign(b)`. – Mankarse Oct 27 '12 at 14:47
  • @Gob00st The other difference is *"For integral operands the / operator yields the algebraic quotient with any fractional part discarded"*, which perfectly specifies the behaviour of `a/b`. So now together with the equation `a = (a/b)*b + a%b`, we get perfectly specified behaviour and there is no need for any implementation-defined behaviour with negative operands. – Christian Rau Oct 27 '12 at 15:08
  • Now I got it after read this & the other post about truncation towards 0 defined in C99(not in C89).Thanks a lot. – RoundPi Oct 27 '12 at 15:24
  • Where can I find the information of changes in C++11 such as the behavior of the modulus operator % ? The websites I've found about the new features of C++ 11 don't mention the changes in the modulus operator. Do I need to buy the C++ Standard from ISO? Isn't this info about C++ available free of charge? – Jorge Luque Mar 06 '16 at 17:10
  • 1
    @JorgeLuque: Technically you need to buy the C++ Standard from ISO of from one of the national standards bodies, but the [final draft of the standard](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf) is freely available, and is usually very very similar to the official standard. See [isocpp.org](https://isocpp.org/std/the-standard). – Mankarse Mar 07 '16 at 01:42
3

The algorithm says (a/b)*b + a%b = a, which is easier to read if you remember that it's truncate(a/b)*b + a%b = a Using algebra, a%b = a - truncate(a/b)*b. That is to say, f(a,b) = a - truncate(a/b)*b. For what values is f(a,b) < 0?

It doesn't matter if b is negative or positive. It cancels itself out because it appears in the numerator and the denominator. Even if truncate(a/b) = 0 and b is negative, well, it's going to be canceled out when it's a product of 0.

Therefore, it is only the sign of a that determines the sign of f(a,b), or a%b.

Bacon Bits
  • 30,782
  • 5
  • 59
  • 66