Menu
We know that for example modulo of power of two can be expressed like this:
x % 2 inpower n == x & (2 inpower n - 1). Examples:
x % 2 == x & 1 x % 4 == x & 3 x % 8 == x & 7 What about general nonpower of two numbers?
Let's say:
x % 7==?
830
Modulo can be easily translated into a bitwise AND if the divisor is a power of two.
The bitwise AND operator ( & ) compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0. Both operands to the bitwise AND operator must have integral types.
Because the bitwise AND operator has both associative and commutative properties, the compiler can rearrange the operands in an expression that contains more than one bitwise AND operator.
First of all, it's actually not accurate to say that
x % 2 == x & 1 Simple counterexample: x = -1. In many languages, including Java, -1 % 2 == -1. That is, % is not necessarily the traditional mathematical definition of modulo. Java calls it the "remainder operator", for example.
With regards to bitwise optimization, only modulo powers of two can "easily" be done in bitwise arithmetics. Generally speaking, only modulo powers of base b can "easily" be done with base b representation of numbers.
In base 10, for example, for non-negative N, N mod 10^k is just taking the least significant k digits.
144
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
