用二进制运算检查除3

本文关键字：检查 二进制运算 | 更新日期: 2023-09-27 18:07:39

我读过这个有趣的答案关于"检查一个数字是否能被3整除"

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

显然我们可以这样做:

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

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

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

为简单起见:

0x55555556L = "1010101010101010101010101010110"

注

还有另一种检查方法:

可以通过数1来判断一个整数是否能被3整除奇数位的位，把这个数乘以2，再加上这个数将偶数位的1位加到结果中并检查是否结果能被3整除

例如:

9310(可被3整除)
01011101 <子> 2

2位在奇数位，4位在偶数位(位是基于2位的0位)

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

一开始我以为这两种方法是有联系的，但是我没有发现其中的联系。

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

-实际上决定是否i%3==0 ?

用二进制运算检查除3

每当你给一个数字加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。但是，如果我们对3取模，这与将c增加2相同。

一个更正式的版本应该是归纳证明。

这两个方法似乎没有关联。按位方法似乎与使用十进制b时有效计算模b-1的某些方法有关，在十进制算术中称为"抛出9"。

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

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对应于232*1/3，这是0x55555555和0x55555556之间的一个数字。由于很快就会明白的原因，我们在这里使用了高估，即四舍五入的结果0x555555556。

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

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:超过这个限制，错误将压倒代表我们结果的最有效分数位。

相关文章：