3 ms·
If you use modulus instead of bitmasking, it doesn't have to be power-of-2 size, does it?
by zimpenfish 10y ago
If you use modulus instead of bitmasking, it doesn't have to be power-of-2 size, does it?
- DblPlusUngood 10y agoNo, the size of the array doesn't need to be a power-of-2 if you use modulus to derive indices. But you need to deal with the overflow somehow. For instance: 0xffffffff % 7 = 3, but (0xffffffff + 1) % 7 = 0.
- RBerenguel 10y agoAlso as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2
- pklausler 10y agoModulus by a power of two is cheap. Modulus by a constant is a multiplication by reciprocal and a shift. And if your argument is in [0..2N], mod N is just a conditional subtraction that doesn't even require a branch.
- CorvusCrypto 10y agocheap is relative right? I mean a multiplication can be spread over shift and add/sub instructions whereas a mask is just one instruction I think right?
- tbirdz 10y agoThat's only true if your compiler actually outputs a modulus instruction when it sees you doing N % pow2. It really should optimize that into N & (pow2-1) for you, so whether you write the & or the % it will end up running the cheap & version.