模运算与按位运算

Question

以下哪种方法更有效(在Scheme中，但我猜这无关紧要)？

(define (lsb n) (- n (bitwise-and n (- n 1))))

(define (lsb n) (remainder n 2))

(对于那些不熟悉Scheme的人。

int lsb (int n)
{
    return n % 2;
}

vs

int lsb (int n)
{
    return n - (n & (n - 1));
}

谢谢!

Answer 1

如果DIV在新的CPU中变得更有效率，那么它肯定不会比如此逐位的操作更快-而且在大多数架构上，可能会把剩余部分打乱(这意味着div指令)。

如果你只关心lsb，为什么不这样写呢：

(define (lsb n)
   (bitwise-and 1 n))

Answer 2

你写错了问题。您正在尝试比较不同函数的性能。例如，对于n == 2，当第2个函数返回2时，第1个函数返回0。

所以，如果你想优化这两个函数，那么它们是：

第一个：

return n & 1;

第二个：

return n & -n;