用二元运算检查除以 3？

Question

我读过 this interesting answer 关于“检查一个数字是否可以被 3 整除”

虽然答案在 Java 中，但它似乎也适用于其他语言。

显然我们可以做到：

boolean canBeDevidedBy3 = (i % 3) == 0;

但有趣的部分是另一个计算：

boolean canBeDevidedBy3 = ((int) (i * 0x55555556L >> 30) & 3) == 0;

为简单起见：

0x55555556L = "1010101010101010101010101010110"

铌

还有另一种检查方法：

One can determine if an integer is divisible by 3 by counting the 1 bits at odd bit positions, multiply this number by 2, add the number of 1-bits at even bit positions add them to the result and check if the result is divisible by 3

例如：

93₁₀（能被3整除）
01011101₂

它在奇数位置有 2 位，在偶数位置有 4 位（位置是基数 2 数字位置的零基）

所以 2*1 + 4 = 6 可以被 3 整除。

起初我以为这两种方法是相关的，但我没有找到。

问题

如何

  boolean canBeDevidedBy3 = ((int) (i * 0x55555556L >> 30) & 3) == 0;

——实际判断是否i%3==0 ?

Answer 1

每当你给一个数字加 3 时，你所做的就是加二进制 11。无论数字的原始值如何，这都将保持不变，即奇数位置 1 的位数的两倍，加上偶数位置 1 的位数，也将被 3 整除。

你可以这样看。我们称上面表达式的值为c。您将 1 添加到奇数位置，将 1 添加到偶数位置。当您将 1 添加到偶数位置时，您添加 1 的位被设置或未设置。如果未设置，您会将 c 的值增加 1，因为您在奇数位置添加了新的 1。如果它之前已设置，您将翻转该位，但在偶数位置（从进位开始）添加 1 。这意味着您最初将 c 减少 1，但现在当您在偶数位置添加 1 时，您将 c 增加 2，因此总体上您增加了 c 2.

当然，这个进位位也可能被添加到一个已经设置的位上，在这种情况下我们需要检查这部分是否仍然将 c 增加 2：你将删除一个 1 在偶数位置（将 c 减 2），然后在奇数位置添加一个 1（将 c 增加 1），这意味着我们实际上已经减少了 c 加 1。这与将 c 加 2 相同，不过，如果我们对 3 求模。

一个更正式的版本将被构造为归纳证明。

Answer 2

这两种方法似乎没有关联。位法似乎与使用数字基数 b 时有效计算模数 b-1 的某些方法有关，在十进制算术中称为 "casting out nines".

基于乘法的方法直接基于除法的定义，通过与倒数的乘法来完成。让 / 表示数学除法，我们有

int_quot = (int)(i / 3)
frac_quot = i / 3 - int_quot = i / 3 - (int)(i / 3)
i % 3 = 3 * frac_quot = 3 * (i / 3 - (int)(i / 3))

商的小数部分直接转化为整数除法的余数：分数为0则余数为0，分数为1/3则余数为1，分数为2/ 3 余数是2。也就是说我们只需要检查商的小数部分。

我们可以乘以 1/3，而不是除以 3。如果我们以 32.32 定点格式执行计算，则 1/3 对应于 2³²*1/3 这是介于 0x55555555 和 0x55555556 之间的数字.出于很快就会明白的原因，我们在这里使用高估，即四舍五入的结果 0x555555556。

当我们将 0x55555556 乘以 i 时，完整 64 位乘积的最高有效 32 位将包含商 (int)(i * 1/3) = [=21= 的整数部分].我们对这个整数部分不感兴趣，所以我们既不计算也不存储它。乘积的低 32 位是小数 0/3、1/3、2/3 之一，但由于我们的 0x555555556 值略大于 1/3:[=34，因此计算时出现轻微错误=]

i = 1:  i * 0.55555556 = 0.555555556
i = 2:  i * 0.55555556 = 0.AAAAAAAAC
i = 3:  i * 0.55555556 = 1.000000002
i = 4:  i * 0.55555556 = 1.555555558
i = 5:  i * 0.55555556 = 1.AAAAAAAAE

如果我们检查二进制中三个可能的小数值的最高有效位，我们会发现 0x5 = 0101、0xA = 1010、0x0 = 0000。因此，商的小数部分的两个最高有效位恰好对应于所需的模值。由于我们正在处理 32 位操作数，因此我们可以通过右移 30 位后跟 0x3 掩码来提取这两位，以隔离两位。我认为 Java 中需要屏蔽，因为 32 位整数总是有符号的。对于 C/C++ 中的 uint32_t 个操作数，仅移位就足够了。

我们现在明白了为什么选择 0x55555555 作为 1/3 的代表是行不通的。商的小数部分将变为 0xFFFFFFF*，并且由于 0xF = 1111 为二进制，因此模计算将产生不正确的结果 3.

请注意，随着 i 幅度的增加，1/3 的不精确表示所产生的累积误差会影响越来越多的小数部分。事实上，详尽的测试表明该方法仅适用于 i < 0x60000000：超出该限制，错误会淹没代表我们结果的最高有效分数位。

用二元运算检查除以 3？

Check division by 3 with binary operations?

java

c#

bit-manipulation

bitwise-operators