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?

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/

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.

ok, i understand, thanks guys!

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

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.

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.

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.

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.