与二进制运算检查除以3？ [英] Check division by 3 with binary operations?

问题描述

我读过的 这个有趣的答案 的关于检查，如果一个数字是被3整除的

虽然答案是在Java中，似乎与其他语言也工作

Although the answer is in Java , it seems to work with other languages also.

显然，我们可以这样做：

Obviously we can do :

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

但最有趣的部分是这样计算的其他：

But the interesting part was this other calculation :

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

为了简单：

0x55555556L =1010101010101010101010101010110

铌

还有要检查它的另一种方法：

There's also another method to check it :

一个可以确定的整数被3整除通过计数1
  在奇数位位置位，乘以2这个数字，加号
  在偶数位位置1位将它们添加到结果，并检查是否
  结果是被3整除

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 ₂

93₁₀ ( is divisible by 3)
01011101₂

它 2 位和 4 在甚至地方位（地方是基于零基本的 2 位位置）

It has 2 bits in the odd places and 4 bits at the even places ( place is the zero based of the base 2 digit location)

所以 2 * 1 + 4 = 6 它通过 3 整除。

起初我还以为那2个方法是相关的，但我怎么没发现。

At first I thought those 2 methods are related but I didn't find how.

问

如何

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

- 实际上决定是否 I％3 == 0

推荐答案

这两种方法似乎不相关。逐位的方法似乎与为模的有效计算某些方法 B-1 使用数字基地时， B ，以十进制算法被称为去九法。

The two methods do not appear to be related. The bit-wise method seems to be related to certain methods for the efficient computation of modulo b-1 when using digit base b, known in decimal arithmetic as "casting out nines".

在与倒数乘法实现基于乘法方法是直接基于划分的定义。让 / 表示数学划分，我们有

The multiplication-based method is directly based on the definition of division when accomplished by multiplication with the reciprocal. Letting / denote mathematical division, we have

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。这意味着我们只需要检查的商的小数部分。

The fractional portion of the mathematical quotient translates directly into the remainder of integer division: If the fraction is 0, the remainder is 0, if the fraction is 1/3 the remainder is 1, if the fraction is 2/3 the remainder is 2. This means we only need to examine the fractional portion of the quotient.

相反除以3，我们可以通过1/3相乘。如果我们在一个32.32定点格式执行计算，1/3对应于2 ³² * 1/3，其是 0x55555555 之间的数和 0x55555556 。其原因将变得明显不久，我们这里使用的高估，这是四舍五入了结果 0x555555556 。

Instead of dividing by 3, we can multiply by 1/3. If we perform the computation in a 32.32 fixed-point format, 1/3 corresponds to 2³²*1/3 which is a number between 0x55555555 and 0x55555556. For reasons that will become apparent shortly, we use the overestimation here, that is the rounded-up result 0x555555556.

当我们乘 0x55555556 按 I ，完整的64位产品的最显著32位将包含商（INT）（我* 1/3） = 的积分部分（INT）（I / 3）。我们不感兴趣，这个积分部分，所以我们既不计算，也不存储。该产品的低32位是分数0/3，1/3，2/3，因为我们的价值有轻微的错误但是计算 0x555555556 略之一大于1/3：

When we multiply 0x55555556 by i, the most significant 32 bits of the full 64-bit product will contain the integral portion of the quotient (int)(i * 1/3) = (int)(i / 3). We are not interested in this integral portion, so we neither compute nor store it. The lower 32-bits of the product is one of the fractions 0/3, 1/3, 2/3 however computed with a slight error since our value of 0x555555556 is slightly larger than 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位整数总是签署。对于 uint32_t的的C / C ++的操作数移位仅此一项就足够了。

If we examine the most significant bits of the three possible fraction values in binary, we find that 0x5 = 0101, 0xA = 1010, 0x0 = 0000. So the two most significant bits of the fractional portion of the quotient correspond exactly to the desired modulo values. Since we are dealing with 32-bit operands, we can extract these two bits with a right shift by 30 bits followed by a mask of 0x3 to isolate two bits. I think the masking is needed in Java as 32-bit integers are always signed. For uint32_t operands in C/C++ the shift alone would suffice.

我们现在看到的，为什么选择 0x55555555 为1/3重presentation是行不通的。商的小数部分将二进制变成 0xFFFFFFF可* ，自 0xF的= 1111 ，模数计算会提供3个不正确的结果。

We now see why choosing 0x55555555 as representation of 1/3 wouldn't work. The fractional portion of the quotient would turn into 0xFFFFFFF*, and since 0xF = 1111 in binary, the modulo computation would deliver an incorrect result of 3.

请注意，由于 I 增加幅度，从IM precise重新$ P $的1/3 psentation累积误差影响了越来越多的位小数部分。事实上，详尽的测试表明，该方法只适用于 I＆LT; 0x60000000 ：超出限制错误压倒从而重新present我们的结果最显著小数位

Note that as i increases in magnitude, the accumulated error from the imprecise representation of 1/3 affects more and more bits of the fractional portion. In fact, exhaustive testing shows that the method only works for i < 0x60000000: beyond that limit the error overwhelms the most significant fraction bits which represent our result.

这篇关于与二进制运算检查除以3？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！