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?

Printable View

- 05-14-2007franzissis 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-2007zacs7
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-2007robatino
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-2007franziss
ok, i understand, thanks guys!

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

- 05-14-2007robatino
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);`

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-2007CornedBee
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.

The programmer, on the other hand, should strive for code that works on both machines. - 05-14-2007brewbuck