按位并代替模数运算符

Question

我们知道,例如两个幂的模数可以这样表达:

  x % 2 inpower n == x & (2 inpower n - 1).

例子:

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7 

两个数字的一​​般非权力怎么样？

让我们说:

x%7 ==？

Answer 1

首先,这实际上并不准确

x % 2 == x & 1

简单的反例:x = -1.在许多语言中,包括Java , -1 % 2 == -1. 也就是说,%不一定是模数的传统数学定义.例如,Java将其称为"余数运算符".

关于按位优化,只能在按位算术中"轻松"完成两个模幂.一般来说,基地只有模权力b可以"轻易"地与基地做b数字表示.

在基数10中,例如,对于非负数N,N mod 10^k仅取最低有效k数字.

参考

• JLS 15.17.3剩余运算符%
• 维基百科/模数操作

Answer 2

目前只有一个简单的方法来找到使用逐2 ^我数模.

根据n%3,n%7这样的链接有一种巧妙的方法来解决Mersenne案例... n%5,n%255和n%6等复合案例都有特殊情况.

对于案例2 ^ i,(2,4,8,16 ...)

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

更复杂的很难解释.只有在你非常好奇的时候才能阅读.

Answer 3

这仅适用于2的幂(并且通常只有正数),因为它们具有在其二进制表示中仅将一个位设置为"1"的唯一属性.因为没有其他类的数字共享此属性,所以无法为大多数模数表达式创建按位和表达式.

Answer 4

这是一个特殊情况,因为计算机代表基数2中的数字.这是可推广的:

(数字)_基数%基数^x

等于(数字)_基数的最后x位数.

Answer 5

除了2的幂之外还存在有效算法的模数.

例如,如果x是32位unsigned int,那么x%3 = popcnt(x&0x55555555) - popcnt(x&0xaaaaaaaa)