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?
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.
Last edited by robatino; 05-14-2007 at 05:11 AM.
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.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
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.
Last edited by robatino; 05-14-2007 at 09:41 AM.
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.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.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law