Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ appears to violate properties of addition

Tags:

c++

Working on an assignment for class, I ran into this (notice the conditional of the loop)

// This one works.
for (int k = 0; k + negwords[j].length() < comments[i].length(); k++) {
    if (comments[i].substr(k, negwords[j].length()) == negwords[j]) {
        negativeScore++;
    }
}
//*/

/*/ This one doesn't: It fails with an out-of-bounds index.
for (int k = 0; k < comments[i].length() - negwords[j].length(); k++) {
    if (comments[i].substr(k, negwords[j].length()) == negwords[j]) {
        negativeScore++;
    }
}
//*/

Why is it that the first one works but the second one doesn't? Is it something about order of operations, bool coercion to int, operator associativity, or an OBOE?

like image 766
Matt G Avatar asked Sep 18 '14 20:09

Matt G


1 Answers

If either negwords[j].length() or comments[i].length() return an unsigned integral type at least as large as unsigned int, then k will be promoted to the same unsigned type, and the rules of modular addition will apply.

As an example, this means that 1 < 2 - 3 is true, because 2 - 3 wraps around in modular arithmetic, becoming a very large number.

If you're interested, this behavior is specified in section 3.9.1 of the Standard, which includes the rule:

Unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer.

And a footnote concerning the implications:

48 This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.


Mathematicians know this type of arithmetic as the algebra of Galois fields. In C++, it's used for unsigned integral types. Other types don't use modular arithmetic, but they also don't use normal grade-school arithmetic (formally, the algebra of real numbers), because normal arithmetic requires a dense uncountable set of numbers, and a computer of finite size can't represent members of an infinite set.

Thanks to Oliver for pointing out my mistake. GF(2)^n does govern the bitwise operations and a whole bunch of other common calculations done in computer software, such as CRC. But it doesn't describe unsigned arithmetic of more than 1 bit, since polynomials on Galois fields don't "carry".

like image 64
Ben Voigt Avatar answered Sep 27 '22 21:09

Ben Voigt