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

Breeding

@Neil - Modulo and Binary And are pretty fundamental operations, I'm guessing they're about the same in any computer language. – Meyerbeer

I do get a bit tired of not seeing the language posted :) Though I guess usually if they don't specify, I assume that means C++ or C. I wonder how true that is.. – Rattling

Just for anyone struggling to understand this, take a look at https://mcmap.net/q/22766/-what-is-the-rationale-behind-x-64-x-amp-63-duplicate. Oh, and in JS with V8 I get a very slight performance boost by using bitwise operators. – Golub

@JamesKolpack A bitwise operation can be performed MUCH faster on a CPU than a modulo. In fact, a common assembly trick to zero a register is to XOR it with itself (because of this fact). Nowadays a compiler might be able to optimize a modulo of a power of two, but I don't know – Bullfinch

Answer 1

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

• JLS 15.17.3 Remainder Operator %
• Wikipedia/Modulo Operation

Borderland

-1 = -1 (mod 2), not sure what you're getting at - you mean it's not the same as the IEEE 754 remainder? – Pipestone

@BlueRaja: the common residue for -1 in mod 2 is 1 en.wikipedia.org/wiki/Modular_arithmetic#Remainders – Borderland

@BlueRaja: If you allow negative numbers, what you basically can be sure of (particularly since no language was mentioned) is that (a / b) / b + a % b == a, for C-type operators, a and b integers, b nonzero, and also that abs(a % b) < abs(b) with the same provisos. – Billfold

@DavidThornley - assume you mean (a / b) * b + a % b == a. – Kuehnel

Answer 2

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.

Updo

n % 2^i = n & (1 << i - 1) – Brathwaite

Answer 3

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.

Callboard

If you happen to be operating on a ternary architecture, then that changes things a bit...chances are about nil however. – Major

I like how you're phrasing it: "that changes things a bit" – Hasid

Answer 4

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

(number)_base % base^x

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

Antechamber

Answer 5

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)

Truesdale

This is the first answer here that actually answers the question. – Gallic

10 % 3 == popcount(0) - popcount(0xA) == -2? – Ankus

Answer 6

Not using the bitwise-and (&) operator in binary, there is not. Sketch of proof:

Suppose there were a value k such that x & k == x % (k + 1), but k != 2^n - 1. Then if x == k, the expression x & k seems to "operate correctly" and the result is k. Now, consider x == k-i: if there were any "0" bits in k, there is some i greater than 0 which k-i may only be expressed with 1-bits in those positions. (E.g., 1011 (11) must become 0111 (7) when 100 (4) has been subtracted from it, in this case the 000 bit becomes 100 when i=4.) If a bit from the expression of k must change from zero to one to represent k-i, then it cannot correctly calculate x % (k+1), which in this case should be k-i, but there is no way for bitwise boolean and to produce that value given the mask.

Tauromachy

Answer 7

Modulo "7" without "%" operator

int a = x % 7;

int a = (x + x / 7) & 7;

Curcuma

Doesn't work for 10 % 2 = 0. ( 10 + 10/2 ) & 2 = 15 & 2 = 2, Similarly 10 % 6 = 4. ( 10 + 10/6) & 6 = 11 & 6 = 2 – Updo

Also, why would you want to divide when you want to avoid using modulo? AFAIK, the instruction to divide is the same as the one to get the remainder. – Highstrung

@SriramMurali Thats because you used an even mod, of course it wouldn't work, this is a workaround for odd like the OP said. – Balzer

Answer 8

In this specific case (mod 7), we still can replace %7 with bitwise operators:

// Return X%7 for X >= 0.
int mod7(int x)
{
  while (x > 7) x = (x&7) + (x>>3);
  return (x == 7)?0:x;
}

It works because 8%7 = 1. Obviously, this code is probably less efficient than a simple x%7, and certainly less readable.

Enchantment

Answer 9

Using bitwise_and, bitwise_or, and bitwise_not you can modify any bit configurations to another bit configurations (i.e. these set of operators are "functionally complete"). However, for operations like modulus, the general formula would be necessarily be quite complicated, I wouldn't even bother trying to recreate it.

Macdermot