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
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.
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
for example? There can be worse cases where the fact that it's a power of two wouldn't be evident from the expression.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.
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.
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.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.