c - 这是编译器仅通过使用位运算来划分的方式吗？

Question

使用位运算符除法

我在 stackoverflow 上发现了一篇帖子，并且 看到了这个奇怪的除以 3 的方法 ( What's the fastest way to divide an integer by 3? )。
它表示:n/3 = (n * 0x55555556) >> 32。即乘以 0x55555556 并取最重要的 32 位。对于 n 是一个 32 位数字，这是正确的。
当我开始挖掘其背后的逻辑时，我意识到这可以推广。例如，如果我们考虑 n < 128；即 7 位宽:
n/3 = (n * 0x56) >> 8。 那么这里发生了什么？那么，0x56 = 86 = (258/3) 和 258 是第一个大于 256 的数字，它可以被 3 整除。现在，
2n = 258n - 256n
==> n = 129n - 128n 对于任何 n;
但是如果限制 n < 128；则 129n - 128n 与 (129n/128) 的商相同。
==> n = 129n/128; n < 128
==> n/3 = 43n/128;对于 n < 128
==> n/3 = 86n/256; n < 128
==> n/3 = (n * 0x56) >> 8;

令人惊奇的是，这可以推广到其他部门。例如考虑除以 5:
4n = 260n - 256n ==> n = 65n - 64n 对于所有 n
如果 n < 64； n = 65n/64
==> n/5 = 13n/64; n < 64
==> n/5 = (13 * n) >> 6;
同样，n/5 = (52 * n) >> 8； n < 64

我们可以按照相同的思路进行推导:
n/5 = 205n/1024 = (205*n) >> 10 对于 n < 1024

所以；我试图找到一个通用规则来为任何 a 找到 n/a ?
首先找到 2 的某个幂(比如 2^m)，它是 a 的倍数的一个差(比如 1024，如果 a = 5)；
即 2^m + 1 = ka；对于一些 k
因此，工作是计算出 k，同时保持 m 固定(例如 32):2^m + 1 = k 一个。对此可以有多种解决方案；一旦 m 固定，就只有一个。

然后; n/a = k*n >> m;对于所有 n < 2^m

这就是编译器的工作方式吗？使用 formula generator由 kol 在其中一条评论中提供:
保持 m=32 和 n=12；公式生成器给出:
a=3: n/3 = (1431655766 * n) >> 32
a=5: n/5 = (858993460 * n) >> 32
a=7: n/7 = (613566757 * n) >> 32

但是，当我看到我的汇编输出时，我得到 1431655766、1717986919 和 -1840700269 除以 3、5 和 7。
此外，如果我将数据类型更改为 unsigned int，则 3,5 和 7 分别得到 -1431655765、-858993459 和 613566757。

---

如你所见；我对除以 3 的预测是正确的，但对于 5 和 7 却失败了。有趣的是看看它们之间的关系有多密切；但我无法解释

---

在分析除法时编译器的作用时我哪里出错了？

---

来自公式生成器的代码(来自kol):

var $a = $("#a"),
$m = $("#m"),
$generate = $("#generate"),
$formula = $("#formula");

$generate.click(function () {
var a = +$a.val(),
    m = +$m.val(),
    m2 = 0,
    k = 0;

if (isNaN(a) || a !== Math.floor(a) || a < 2 || a > Math.pow(2, 31) - 1) {
    alert("Divisor \"a\" must be an integer between 2 and 2^32-1");
    return;
}
m2 = Math.pow(2, m);
k = Math.ceil(m2 / a);
$formula.html("<i>n</i> / " + a + " = (" + k + " * <i>n</i>) &gt;&gt; " + m + "; for all <i>n</i> &lt; " + m2);
});

$generate.click();

Answer 1

不，C 编译器不使用按位运算进行算术运算。即使在汇编中，您也不必使用按位运算进行算术运算。当然，它在处理器上以这种方式工作，处理器提供此处描述的命令:http://en.wikibooks.org/wiki/X86_Assembly/Arithmetic作为这些操作的抽象。