# is mod(%) efficient?

• 05-14-2007
franziss
is mod(%) efficient?
I understand that using shifting bits to do multiplication is fast.

but what a mod? is using the standard mod fast? can i do shifting bits to do mod?
• 05-14-2007
zacs7
Mod is slow in comparison to other operations, and yes you can use bitwise ops to a certain extent to do modulus.
http://snipplr.com/view/2431/test-if...wise-operator/
• 05-14-2007
robatino
You can find the remainder of an unsigned number mod any power of two with bitwise operators - for example, the remainder mod 64 is the result of a bitwise & with 63.

Edit: And the quotient is the result of a bitwise right shift by 6. In general, you can get both the quotient and remainder for a power of two this way. For the general case, there's div(), ldiv(), lldiv(), and imaxdiv() which let you compute the quotient and remainder simultaneously.
• 05-14-2007
franziss
ok, i understand, thanks guys!
• 05-14-2007
CornedBee
And don't do any of this bit stuff. If it can be done, the compiler will notice it and do it.
• 05-14-2007
robatino
Quote:

Originally Posted by CornedBee
And don't do any of this bit stuff. If it can be done, the compiler will notice it and do it.

Unless the number in question is a variable that happens to always be a power of two, but the compiler doesn't know it. Are compilers typically smart enough to optimize something like
Code:

`  m &#37;= (1 << n);`
for example? There can be worse cases where the fact that it's a power of two wouldn't be evident from the expression.

Edit: Also, I'd agree that something like m & 63 may be a little confusing (mostly because the constant isn't in binary - octal or hexadecimal would be better), but m & 1 is perfectly intuitive - a (unsigned?) number is odd iff its 1's bit is 1.
• 05-14-2007
CornedBee
Quote:

Originally Posted by robatino
Unless the number in question is a variable that happens to always be a power of two, but the compiler doesn't know it. Are compilers typically smart enough to optimize something like
Code:

`  m %= (1 << n);`
for example?

Do you actually have such cases? Do you know in these cases that it will always be a power of two? In the typical case, such optimizations are done by the programmer only when the number is a constant anyway.

And even if there is a complicated expression that you know is a power of two, you still should use modulo unless profiling proves that you really have a bottleneck there.

Quote:

Edit: Also, I'd agree that something like m & 63 may be a little confusing (mostly because the constant isn't in binary - octal or hexadecimal would be better), but m & 1 is perfectly intuitive - a number is odd iff its 1's bit is 1.
Perfectly intuitive and perfectly unportable: it's the other way round for negative numbers on a 1's complement machine. Which is part of what I meant by "if it can be done": the compiler knows if it's on a 1's complement or a 2's complement machine and can choose to do this optimization depending on this knowledge.
The programmer, on the other hand, should strive for code that works on both machines.
• 05-14-2007
brewbuck
Quote:

Originally Posted by CornedBee
Perfectly intuitive and perfectly unportable: it's the other way round for negative numbers on a 1's complement machine.

This will change in C99.

EDIT: Wait. We're talking about ANDing at this point, not modulus. Nevermind.