147

I always assumed that when doing (a % 256) the optimizer would naturally use an efficient bitwise operation, as if I wrote (a & 0xFF).

When testing on compiler explorer gcc-6.2 (-O3):

// Type your code here, or load an example.
int mod(int num) {
    return num % 256;
}

mod(int):
    mov     edx, edi
    sar     edx, 31
    shr     edx, 24
    lea     eax, [rdi+rdx]
    movzx   eax, al
    sub     eax, edx
    ret

And when trying the other code:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Seems like I'm completely missing something out. Any ideas?

21
  • 64
    0xFF is 255 not 256. Nov 8, 2016 at 9:30
  • 188
    @RishikeshRaje: So? % is not & either.
    – Jongware
    Nov 8, 2016 at 9:30
  • 27
    @RishikeshRaje: I am sure the OP is very much aware of that. They're used with different operations. Nov 8, 2016 at 9:31
  • 28
    Out of interest, do you get better results if num is unsigned?
    – Bathsheba
    Nov 8, 2016 at 9:32
  • 21
    @RishikeshRaje Bitwise and 0xFF is equivalent to modulo 2^8 for unsigned integers.
    – 2501
    Nov 8, 2016 at 9:50

5 Answers 5

231

It's not the same. Try num = -79, and you will get different results from both operations. (-79) % 256 = -79, while (-79) & 0xff is some positive number.

Using unsigned int, the operations are the same, and the code will likely be the same.

PS- Someone commented

They shouldn't be the same, a % b is defined as a - b * floor (a / b).

That's not how it is defined in C, C++, Objective-C (ie all the languages where the code in the question would compile).

1
55

Short answer

-1 % 256 yields -1 and not 255 which is -1 & 0xFF. Therefore, the optimization would be incorrect.

Long answer

C++ has the convention that (a/b)*b + a%b == a, which seems quite natural. a/b always returns the arithmetic result without the fractional part (truncating towards 0). As a consequence, a%b has the same sign as a or is 0.

The division -1/256 yields 0 and hence -1%256 must be -1 in order to satisfy the above condition ((-1%256)*256 + -1%256 == -1). This is obviously different from -1&0xFF which is 0xFF. Therefore, the compiler cannot optimize the way you want.

The relevant section in the C++ standard [expr.mul §4] as of N4606 states:

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 [...].

Enabling the optimization

However, using unsigned types, the optimization would be completely correct, satisfying the above convention:

unsigned(-1)%256 == 0xFF

See also this.

Other languages

This is handled very different across different programming languages as you can look up on Wikipedia.

0
50

Since C++11, num % 256 has to be non-positive if num is negative.

So the bit pattern would depend on the implementation of signed types on your system: for a negative first argument, the result is not the extraction of the least significant 8 bits.

It would be a different matter if num in your case was unsigned: these days I'd almost expect a compiler to make the optimisation that you cite.

11
  • 6
    Almost but not quite. If num is negative, then num % 256 is zero or negative (a.k.a. non-positive).
    – Nayuki
    Nov 8, 2016 at 15:16
  • 5
    Which IMO, is a mistake in the standard: mathematically modulo operation should take the sign of the divisor, 256 in this case. In order to understand why consider that (-250+256)%256==6, but (-250%256)+(256%256) must be, according to the standard, "non-positive", and therefore not 6. Breaking associativity like that has real life side effects: for example when computing "zooming out" rendering in integer coordinates one has to shift the image to have all coordinates non-negative.
    – Michael
    Nov 8, 2016 at 17:13
  • 2
    @Michael Modulus has never been distributive over addition ("associative" is the wrong name for this property!), even if you follow the math definition to the letter. For example, (128+128)%256==0 but (128%256)+(128%256)==256. Perhaps there's a good objection to the specified behavior, but it isn't clear to me that it's the one you said. Nov 8, 2016 at 17:23
  • 1
    @DanielWagner, you are right, of course, I misspoke with "associative". However, if one keeps the sign of the divisor and computes everything in modular arithmetic, the distributive property does hold; in your example you would have 256==0. The key is to have exactly N possible values in modulo N arithmetic, which is only possible if all the results are in the range 0,...,(N-1), not -(N-1),...,(N-1).
    – Michael
    Nov 8, 2016 at 18:27
  • 6
    @Michael: Except % is not a modulo operator, it's a remainder operator.
    – Joren
    Nov 9, 2016 at 12:20
11

I don't have telepathic insight into the compiler's reasoning, but in the case of % there is the necessity of dealing with negative values (and division rounds towards zero), while with & the result is always the lower 8 bits.

The sar instruction sounds to me like "shift arithmetic right", filling up the vacated bits with the sign bit value.

0
0

As others have pointed out:

If you like me want the modulo operation to actually output a positive integer, as in my use case where I convert a hue (hsv color space) double where 1.0 == 360 degrees to a unsigned char by multiplying with 255.0, taking the floor followed by modulo 256. Then &0xff is a correct optimization. Observe that I treat 255 as 360 degrees to fit into unsigned char in my case.

hue = [-1.0 , 2.0]
hue = (unsigned char)(floor(hue * 255.0) & 0xff)

But this might not be the right solution for your specific use case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.