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  amp   2 inpower n - 1     Examples   x   2    x  amp  1 x   4    x  amp  3 x   8    x  amp  7    What about general nonpower of two numbers   Let s say   x   7

User · Answer

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  amp   2 i - 1    More complicated ones are hard to explain  Read up only if you are very curious

User · Answer

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

User · Answer

First of all  it s actually not accurate to say that  x   2    x  amp  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

User · Answer

Not using the bitwise-and   amp   operator in binary  there is not   Sketch of proof   Suppose there were a value k such that x  amp  k    x    k   1   but k    2 n - 1   Then if x    k  the expression x  amp  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

User · Answer

In this specific case  mod 7   we still can replace  7 with bitwise operators      Return X 7 for X  gt   0  int mod7 int x      while  x  gt  7  x    x amp 7     x gt  gt 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

User · Answer

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

User · Answer

Modulo  7  without     operator  int a   x   7   int a    x   x   7   amp  7

User · Answer

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  amp  0x55555555  - popcnt  x  amp  0xaaaaaaaa

User · Answer

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

[algorithm] Bitwise and in place of modulus operator

Examples related to algorithm