Advertisement
Advertisement


Bitwise and in place of modulus operator


Question

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==?

2010/07/24
1
88
7/24/2010 3:28:01 PM

Accepted Answer

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.

References

2010/06/18
67
6/18/2010 8:03:37 PM

There is only a simple way to find modulo of 2^i numbers using bitwise.

There is an ingenious way to solve Mersenne cases as per the link such as n % 3, n % 7... There are special cases for n % 5, n % 255, and composite cases such as n % 6.

For cases 2^i, ( 2, 4, 8, 16 ...)

n % 2^i = n & (2^i - 1)

More complicated ones are hard to explain. Read up only if you are very curious.

2013/11/04

This only works for powers of two (and frequently only positive ones) because they have the unique property of having only one bit set to '1' in their binary representation. Because no other class of numbers shares this property, you can't create bitwise-and expressions for most modulus expressions.

2010/06/18

This is specifically a special case because computers represent numbers in base 2. This is generalizable:

(number)base % basex

is equivilent to the last x digits of (number)base.

2010/06/18

There are moduli other than powers of 2 for which efficient algorithms exist.

For example, if x is 32 bits unsigned int then x % 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

2010/06/20

Modulo "7" without "%" operator

int a = x % 7;

int a = (x + x / 7) & 7;
2018/03/16

Source: https://stackoverflow.com/questions/3072665
Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]