CODEWITHSUNDEEP
javaoptimization
ixron
ixron

Reputation: 127

How to use bit shifting for modulus?

I have just started to use bit shifting to optimize some of my code for SPOJ programming problems. I am looking for how to do this with modulus. Does anyone have any suggestions or links to information that could be of any help?

Upvotes: 0

Views: 1593

Answers (2)

catfood
catfood

Reputation: 4341

I hope this isn't insultingly basic, but bit-masking (not really bit-shifting) for modulus will only work for divisors that are powers of 2. So the bit-masking technique tends to be useful only in a subset of situations in which you know in advance what the divisor will be.

Also, if you can hardcode the divisor--that's usually a case where the compiler will optimize the calculation as well as you can anyway.

Upvotes: 1

user149341
user149341

Reputation:

There is no way to use bit shifting for a modulus operation. Bit shifting is more akin to division than modulus.

Bitwise AND can be used for some very simple modulus operations (e.g, & 3 instead of % 4), but the speedup is pretty minimal, and an optimizing JRE is likely to make that optimization on its own already.

Upvotes: 3

Related Questions