# Modulus without modulus operator.

## Recommended Posts

Dirge    300
So I'm implementing a new bit stream (bit packing) class similar to what Jonathan Blow presented in his old gd mag articles and I've run into a performance concern when "un-packing" a value from the stream. Specifically there's a very intensive loop that for every bit in a value does a divide then modulus to get the byte and bit indices. Now for a 32-bit integer this is happening 32 times and for many iterations (this is for network data transmission code). I remember reading back a while ago that there is a way to do a modulus operation without having to actually call the operator but taking into account a few bit tricks when using integers. Can anyone point me to this information or explain how this might work. Your help is greatly appreciated and I thank you ahead of time.

##### Share on other sites
wyrzy    430
I think you can find what you're looking for at:
http://graphics.stanford.edu/~seander/bithacks.html

##### Share on other sites
Raghar    96
Quote:
 Original post by DirgeSo I'm implementing a new bit stream (bit packing) class similar to whatthere's a very intensive loop that for every bit in a value does a divide then modulus to get the byte and bit indices. Now for a 32-bit integer this is happening 32 times and for many iterations (this is for network data transmission code).Your help is greatly appreciated and I thank you ahead of time.

Could I ask you why are you using modulo AT ALL? You want to work with 32 bit register thus you need JUST register operations, not math. (even children that never learned modular arithmetic are able to do that)

While you might be confused by saying the bit shifts and other works are in some cases similar to modular arithmetic, bit shifts are of course preferable, not only in computer programming, but also in scientific works.

It looks you'd like to use just bits.
So it is probably something like

mov ebx, eax
shr ebx, ecx
and ebx, 0x1

in 64 assembly

mov rbx, rax
shr rbx, rcx
and rbx, 0x1

b = a & lookUpTable[c];
b >>>= d;
b &= lookUpTableB[d];

or this case, it would be better for you

b = (a >>> c) & 0x1;

Imagine registers as a boxes, and use pins to learn by practicing all registry operations.

##### Share on other sites
Dirge    300
Quote:
 Original post by wyrzyI think you can find what you're looking for at:http://graphics.stanford.edu/~seander/bithacks.html

That was exactly what I was looking for, I have no clue how my searchs didn't find it. Thanks wyrzy!