Sign in to follow this  

Modulus without modulus operator.

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Quote:
Original post by Dirge
So I'm implementing a new bit stream (bit packing) class similar to what

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).

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 this post


Link to post
Share on other sites
Quote:
Original post by wyrzy
I 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!

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this