Is Modulus or Remainder % Signed Value Always the same as And Operator Minus 1 from that value?

Question

Here is some example code

int test = 1234;
int modValue, andValue;
modValue = test % -8;
andValue = test & 7;
printf("Mod Value = %d And Value = %d\n", modValue, andValue);

int counter = 0;
for(counter = 0; counter < 10000; counter++) {
    modValue = counter % -8;
    andValue = counter & 7;
    if(modValue != andValue) {
        printf("diff found at %d\n", counter);
    }
}

Ideone link: http://ideone.com/g79yQm

Negative numbers give different results, that's about it but other then that do they always both function exactly the same for all positive values?

Even for negative numbers they seem to be offsetted only always just off by 1 cyclic round.

Those wondering it's similar to this question Why is modulo operator necessary? question but I don't subtract 1.

This uses negative values which are higher then the modulus value and yeah only works for positive values.

I found this from the IDA-PRO Hex-Ray's decompiler seems to generate sometimes a Modulus % and other times a AND & operator for both identical source codes afaik in different functions. I guess it's from the optimizer.

Since this project I decompiled shouldn't even use negative values I wonder what was the original source code doubt anyone uses modulus with negative values though seems weird.

Also using And as a modulus command how I know cyclic operation always use a modulus yet in this case the person must of used a Val And 7 since Val % 7 is completely different result.

Forgot to say the original code most likely used abs(Val) and 7 since anything with modulus with positive values seems to be wrong I don't think anyone would be using modulus with negative values it looks unappealing to the eyes. So I guess that's the best it could be.

Minor note: The C spec calls `%` the remainder operator. – chux - Reinstate Monica Apr 26 '14 at 14:31 — chux - Reinstate Monica, Apr 26 '14 at 14:31

score 6 · Accepted Answer · answered Apr 26 '14 at 14:28

6

The optimization of x % N to x & (N-1) only works if N is a power of two.

You also need to know that x is positive, otherwise there is a little difference between the bitmask operation and the remainder operation. The bitmask operation produces the remainder for the Euclidean division, which is always positive, whereas % produces the remainder for C's division /, which rounds towards zero and produces a remainder that is sometimes negative.

answered Apr 26 '14 at 14:28

Pascal Cuoq

79,187
7
161
281

Thanks yeah seems to work only for powers of 2, didn't check that. What you mean rounds towards 0 and produces remainder that is sometimes negative? you mean that's why % has a negative value after it? how did it get produced? it wasn't even modulus to begin with you're saying it was a division or some kind to begin with? I don't think it was `x%7` originally as the results are different. – user3435580 Apr 26 '14 at 14:37
@user3435580 The result of `a % b` is defined with respect to the result of `a / b` : “If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.” (6.5.5:6 in the C99 standard). Furthermore, `a / b` is defined differently in C than the Euclidean division is defined in maths: `(-4)/3` is C produces `-1`. Because of this, `(-4) % 3` in C produces `-1`, instead of 2 as you might have expected. And similarly `(-5) % 4` produces `-1`, whereas `(-5) & 3` produces 3 on a typical 2's complement platform. – Pascal Cuoq Apr 26 '14 at 14:41
O wow thats pretty odd I always had a fix that `((n%3)+3)%3;` works for all now haha. I never seen the % as math to be honest I see it as just to make numbers have a cut off where they start to overflow and repeat. Still wondering what do you think the original code most likely looked like the most simplest. – user3435580 Apr 26 '14 at 14:48

lrobb · Answer 2 · 2014-04-26T14:44:50.833

1

The sign of the result of % are machine dependent for negative operands, the same applies for overflow/underflow. / by proxy follows the same rules.

edited Apr 26 '14 at 14:44

answered Apr 26 '14 at 14:30

lrobb

82
10

C99 does define `/` as rounding towards zero (there is nothing platform-dependant about it). It was only implementation-defined in C89 (and no platform ever implemented anything other than rounding towards 0, hence the reinforcement of the specification in C99). `%` is of course defined with respect to `/` in all cases. – Pascal Cuoq Apr 26 '14 at 14:33
@PascalCuoq I did not know that. It's quite interesting, actually. – lrobb Apr 26 '14 at 14:35
1

@Pascal Cuoq agree about C99, but BITD did come across a major platform that did not round towards 0. Thankfully, do not have to cope with that these days - nor remember that outlier. – chux - Reinstate Monica Apr 26 '14 at 14:36
So I have to avoid using % with negative numbers or else it will malfunction on a different kind of machine you're saying. Nevermind seems Pascal Cuoq corrected you and it won't malfunction I hope. – user3435580 Apr 26 '14 at 14:52
@chux which machine was that, can't find anything on google about a "machine that doesn't divide down to zero" I guess it has a more scientific wording. You saying like `100%0` ? – user3435580 Apr 26 '14 at 15:01
Well, @PascalCuoq rightly pointed 99% of hardware today will round down to zero, which was adopted in C99, I believe C++11 adopted these rules, too. If you wanted to be 100% sure, you could do `n < 0 ? x | -b : x & (b-1)` – lrobb Apr 26 '14 at 15:03
1

@user3435580 A 1987-1993 machine (Is was one of HP-UX, IRIX, Novell NetWare, SunOS, AIX) busted other-wise portable programs because of that. http://en.wikipedia.org/wiki/Timeline_of_operating_systems – chux - Reinstate Monica Apr 26 '14 at 17:45

Is Modulus or Remainder % Signed Value Always the same as And Operator Minus 1 from that value?

2 Answers2