一尘不染

按位代替模运算符

algorithm

我们知道例如2的幂的模可以这样表示:

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

例子:

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

一般两个数的无幂呢?

比方说:

x%7 ==?


阅读 218

收藏
2020-07-28

共1个答案

一尘不染

首先,说这实际上是不准确的

x % 2 == x & 1

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

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

例如,对于非负数N,以10为底N mod 10^k仅取最低有效k数字。

参考资料

2020-07-28