# Modulus without modulus operator.

This topic is 4352 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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
I think you can find what you're looking for at:
http://graphics.stanford.edu/~seander/bithacks.html

##### Share on other sites
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
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!

1. 1
2. 2
Rutin
21
3. 3
JoeJ
18
4. 4
gaxio
12
5. 5

• 14
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631724
• Total Posts
3001896
×