def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
There's a fairly well-known trick for determining whether a number is a multiple of 11, by alternately adding and subtracting its decimal digits. If the number you get at the end is a multiple of 11, then the number you started out with is also a multiple of 11:
We can apply the same trick to binary numbers. A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3:
It makes no difference whether you start with the MSB or the LSB, so the following Python function works equally well in both cases. It takes an iterator that returns the bits one at a time. multiplier alternates between 1 and 2 instead of 1 and -1 to avoid taking the modulo of a negative number.
def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
Here... something new... how to check if a binary number of any length (even thousands of digits) is divisible by 3.
-->((0))<---1--->()<---0--->(1) ASCII representation of graph
From the picture.
You start in the double circle.
When you get a one or a zero, if the digit is inside the circle, then you stay in that circle. However if the digit is on a line, then you travel across the line.
Repeat step two until all digits are comsumed.
If you finally end up in the double circle then the binary number is divisible by 3.
You can also use this for generating numbers divisible by 3. And I wouldn't image it would be hard to convert this into a circuit.
1 example using the graph...
11000000000001011111111111101 is divisible by 3 (ends up in the double circle again)
Try it for yourself.
You can also do similar tricks for performing MOD 10, for when converting binary numbers into base 10 numbers. (10 circles, each doubled circled and represent the values 0 to 9 resulting from the modulo)
EDIT: This is for digits running left to right, it's not hard to modify the finite state machine to accept the reverse language though.
NOTE: In the ASCII representation of the graph () denotes a single circle and (()) denotes a double circle. In finite state machines these are called states, and the double circle is the accept state (the state that means its eventually divisible by 3)
S' 与上面不同，但 O 的工作方式相同，因为对于相同情况（00 和 11），S' 为 0。 由于 O 在两种情况下相同，O_LSB = O_MSB，因此要使 MSB 与 LSB 一样短，反之亦然，只需使用两者中最短的一个即可。
Heh
State table for LSB:
S I S' O
0 0 0 1
0 1 1 0
1 0 2 0
1 1 0 1
2 0 1 0
2 1 2 0
Explanation: 0 is divisible by three. 0 << 1 + 0 = 0. Repeat using S = (S << 1 + I) % 3 and O = 1 if S == 0.
State table for MSB:
S I S' O
0 0 0 1
0 1 2 0
1 0 1 0
1 1 0 1
2 0 2 0
2 1 1 0
Explanation: 0 is divisible by three. 0 >> 1 + 0 = 0. Repeat using S = (S >> 1 + I) % 3 and O = 1 if S == 0.
S' is different from above, but O works the same, since S' is 0 for the same cases (00 and 11). Since O is the same in both cases, O_LSB = O_MSB, so to make MSB as short as LSB, or vice-versa, just use the shortest of both.
这也是解决问题 c) 的一个想法。 如果反转二进制整数的位顺序，则所有位都保持在偶数/奇数位置，或者所有位都会改变。 因此，反转整数 n 的位顺序的结果是一个可被 3 整除的整数，当且仅当 n 可被 3 整除时。因此，问题 a) 的任何解决方案都可以在不改变问题 b) 的情况下工作，反之亦然。 嗯，也许这可以帮助找出哪种方法更快......
Here is an simple way to do it by hand. Since 1 = 22 mod 3, we get 1 = 22n mod 3 for every positive integer. Furthermore 2 = 22n+1 mod 3. Hence 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 posistions add them to the result and check if the result is divisible by 3.
Example: 5710=1110012. There are 2 bits at odd positions, and 2 bits at even positions. 2*2 + 2 = 6 is divisible by 3. Hence 57 is divisible by 3.
Here is also a thought towards solving question c). If one inverts the bit order of a binary integer then all the bits remain at even/odd positions or all bits change. Hence inverting the order of the bits of an integer n results is an integer that is divisible by 3 if and only if n is divisible by 3. Hence any solution for question a) works without changes for question b) and vice versa. Hmm, maybe this could help to figure out which approach is faster...
last | n is even? | input || next | example
-------------------------------------------
d/c | don't care | 0 || last | last + 0*2^n = last
0 | yes | 1 || 0 | 0 + 1*2^n = 1 (= 2^n mod 3)
0 | no | 1 || 0 | 0 + 1*2^n = 2 (= 2^n mod 3)
1 | yes | 1 || 0 | 1 + 1*2^n = 2
1 | no | 1 || 0 | 1 + 1*2^n = 0 (= 3 mod 3)
1 | yes | 1 || 0 | 2 + 1*2^n = 0
1 | no | 1 || 0 | 2 + 1*2^n = 1
The idea is that the number can grow arbitrarily long, which means you can't use mod 3 here, since your number will grow beyond the capacity of your integer class.
The idea is to notice what happens to the number. If you're adding bits to the right, what you're actually doing is shifting left one bit and adding the new bit.
Shift-left is the same as multiplying by 2, and adding the new bit is either adding 0 or 1. Assuming we started from 0, we can do this recursively based on the modulo-3 of the last number.
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
unsigned value = 0;
char *p = input;
if (*p == '1') {
value &= 1;
}
p++;
while (*p) {
if (*p != ',') {
value <<= 1;
if (*p == '1') {
ret &= 1;
}
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
LSB 方法：
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
unsigned value = 0;
unsigned mask = 1;
char *p = input;
while (*p) {
if (*p != ',') {
if (*p == '1') {
value &= mask;
}
mask <<= 1;
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
就我个人而言，我很难相信其中一种方法与另一种方法有显着不同。
Actually the LSB method would actually make this easier. In C:
MSB method:
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
unsigned value = 0;
char *p = input;
if (*p == '1') {
value &= 1;
}
p++;
while (*p) {
if (*p != ',') {
value <<= 1;
if (*p == '1') {
ret &= 1;
}
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
LSB method:
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
unsigned value = 0;
unsigned mask = 1;
char *p = input;
while (*p) {
if (*p != ',') {
if (*p == '1') {
value &= mask;
}
mask <<= 1;
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
Personally I have a hard time believing one of these will be significantly different to the other.
我认为 Nathan Fellman 对于 a 和 b 部分来说是正确的（除了 b 需要一个额外的状态：你需要跟踪你的数字位置是奇数还是偶数）。
我认为 C 部分的技巧是在每一步否定 last 值。 即0到0，1到2，2到1。
I think Nathan Fellman is on the right track for part a and b (except b needs an extra piece of state: you need to keep track of if your digit position is odd or even).
I think the trick for part C is negating the last value at each step. I.e. 0 goes to 0, 1 goes to 2 and 2 goes to 1.
发布评论
评论（10）
有一个相当著名的技巧，可以通过交替加减十进制数字来确定一个数字是否是 11 的倍数。 如果最后得到的数字是 11 的倍数，那么一开始的数字也是 11 的倍数：
我们可以将相同的技巧应用于二进制数。 当且仅当其位的交替和也是 3 的倍数时，二进制数才是 3 的倍数：
无论从 MSB 还是 LSB 开始都没有区别，因此以下 Python 函数在这两种情况下都同样有效。 它需要一个每次返回一位的迭代器。
multiplier在 1 和 2 之间交替，而不是 1 和 -1，以避免取负数的模。There's a fairly well-known trick for determining whether a number is a multiple of 11, by alternately adding and subtracting its decimal digits. If the number you get at the end is a multiple of 11, then the number you started out with is also a multiple of 11:
We can apply the same trick to binary numbers. A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3:
It makes no difference whether you start with the MSB or the LSB, so the following Python function works equally well in both cases. It takes an iterator that returns the bits one at a time.
multiplieralternates between 1 and 2 instead of 1 and -1 to avoid taking the modulo of a negative number.这里...一些新内容...如何检查任意长度（甚至数千位）的二进制数是否可以被 3 整除。
从图片中。
你也可以用它来生成可以被 3 整除的数字。而且我不认为将它转换成电路会很困难。
1 个使用图表的示例...
11000000000001011111111111101 能被 3 整除（再次出现在双圆圈中）
自己尝试一下。
当将二进制数转换为以 10 为基数的数字时，您还可以执行类似的技巧来执行 MOD 10。 （10 个圆圈，每个圆圈都加倍，代表模数产生的值 0 到 9）
编辑：这是针对从左到右运行的数字，修改有限状态机以接受相反的情况并不难虽然语言。
注意： 在图形的 ASCII 表示中，() 表示单圆，(()) 表示双圆。 在有限状态机中，这些被称为状态，双圆圈是接受状态（该状态意味着它最终可以被 3 整除）
Here... something new... how to check if a binary number of any length (even thousands of digits) is divisible by 3.
From the picture.
You can also use this for generating numbers divisible by 3. And I wouldn't image it would be hard to convert this into a circuit.
1 example using the graph...
11000000000001011111111111101 is divisible by 3 (ends up in the double circle again)
Try it for yourself.
You can also do similar tricks for performing MOD 10, for when converting binary numbers into base 10 numbers. (10 circles, each doubled circled and represent the values 0 to 9 resulting from the modulo)
EDIT: This is for digits running left to right, it's not hard to modify the finite state machine to accept the reverse language though.
NOTE: In the ASCII representation of the graph () denotes a single circle and (()) denotes a double circle. In finite state machines these are called states, and the double circle is the accept state (the state that means its eventually divisible by 3)
Heh
LSB 的状态表：
说明：0 能被三整除。 <代码>0 << 1 + 0 = 0。 如果
S == 0，则重复使用S = (S << 1 + I) % 3和O = 1。MSB 的状态表：
说明：0 能被三整除。 <代码>0>> 1 + 0 = 0。 如果
S == 0，则重复使用S = (S >> 1 + I) % 3和O = 1。S'与上面不同，但 O 的工作方式相同，因为对于相同情况（00 和 11），S'为 0。 由于 O 在两种情况下相同，O_LSB = O_MSB，因此要使 MSB 与 LSB 一样短，反之亦然，只需使用两者中最短的一个即可。Heh
State table for LSB:
Explanation: 0 is divisible by three.
0 << 1 + 0 = 0. Repeat usingS = (S << 1 + I) % 3andO = 1ifS == 0.State table for MSB:
Explanation: 0 is divisible by three.
0 >> 1 + 0 = 0. Repeat usingS = (S >> 1 + I) % 3andO = 1ifS == 0.S'is different from above, but O works the same, sinceS'is 0 for the same cases (00 and 11). Since O is the same in both cases, O_LSB = O_MSB, so to make MSB as short as LSB, or vice-versa, just use the shortest of both.这是一种手动完成的简单方法。
由于 1 = 22 mod 3，对于每个正整数，我们得到 1 = 22n mod 3。
此外，2 = 22n+1 mod 3。因此，可以通过计算奇数位位置上的 1 位来确定整数是否可以被 3 整除，然后将该数字乘以 2，加上 1- 的数量偶数位位置的位将它们添加到结果中，并检查结果是否能被 3 整除。
示例：5710=1110012。
奇数位置有 2 位，偶数位置有 2 位。 2*2 + 2 = 6 可以被 3 整除。因此 57 可以被 3 整除。
这也是解决问题 c) 的一个想法。 如果反转二进制整数的位顺序，则所有位都保持在偶数/奇数位置，或者所有位都会改变。 因此，反转整数 n 的位顺序的结果是一个可被 3 整除的整数，当且仅当 n 可被 3 整除时。因此，问题 a) 的任何解决方案都可以在不改变问题 b) 的情况下工作，反之亦然。 嗯，也许这可以帮助找出哪种方法更快......
Here is an simple way to do it by hand.
Since 1 = 22 mod 3, we get 1 = 22n mod 3 for every positive integer.
Furthermore 2 = 22n+1 mod 3. Hence 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 posistions add them to the result and check if the result is divisible by 3.
Example: 5710=1110012.
There are 2 bits at odd positions, and 2 bits at even positions. 2*2 + 2 = 6 is divisible by 3. Hence 57 is divisible by 3.
Here is also a thought towards solving question c). If one inverts the bit order of a binary integer then all the bits remain at even/odd positions or all bits change. Hence inverting the order of the bits of an integer n results is an integer that is divisible by 3 if and only if n is divisible by 3. Hence any solution for question a) works without changes for question b) and vice versa. Hmm, maybe this could help to figure out which approach is faster...
您需要使用算术模 3 进行所有计算。这就是
MSB:
LSB:
这是一般想法...
现在，您的任务是理解为什么这是正确的。
是的，你自己做作业;)
You need to do all calculations using arithmetic modulo 3. This is the way
MSB:
LSB:
This is general idea...
Now, your part is to understand why this is correct.
And yes, do homework yourself ;)
这个想法是数字可以任意增长，这意味着你不能在这里使用
mod 3，因为你的数字将增长超出你的整数类的容量。这个想法是注意数字发生了什么。 如果您要向右添加位，那么您实际上所做的就是向左移动一位并添加新位。
左移与乘以 2 相同，添加新位要么加 0，要么加 1。假设我们从 0 开始，我们可以根据最后一个数字的模 3 递归地执行此操作。
现在让我们看看向左添加一点会发生什么。 首先，请注意：
22n mod 3 = 1
和
22n+1 mod 3 = 2
所以现在我们必须根据 if 在 mod 中添加 1 或 2当前迭代是奇数或偶数。
The idea is that the number can grow arbitrarily long, which means you can't use
mod 3here, since your number will grow beyond the capacity of your integer class.The idea is to notice what happens to the number. If you're adding bits to the right, what you're actually doing is shifting left one bit and adding the new bit.
Shift-left is the same as multiplying by 2, and adding the new bit is either adding 0 or 1. Assuming we started from 0, we can do this recursively based on the modulo-3 of the last number.
Now let's see what happens when you add a bit to the left. First, notice that:
22n mod 3 = 1
and
22n+1 mod 3 = 2
So now we have to either add 1 or 2 to the mod based on if the current iteration is odd or even.
最后一个输入不应该是
12，还是我误解了这个问题？shouldn't this last input be
12, or am i misunderstanding the question?实际上，LSB 方法实际上会使这变得更容易。 在 C 中：
MSB 方法：
LSB 方法：
就我个人而言，我很难相信其中一种方法与另一种方法有显着不同。
Actually the LSB method would actually make this easier. In C:
MSB method:
LSB method:
Personally I have a hard time believing one of these will be significantly different to the other.
如果一个数字的各位数字之和能被 3 整除，则它能被 3 整除。
因此，您可以将数字相加并得到总和：
A number is divisible by 3 if the sum of it's digits is divisible by 3.
So you can add the digits and get the sum:
我认为 Nathan Fellman 对于 a 和 b 部分来说是正确的（除了 b 需要一个额外的状态：你需要跟踪你的数字位置是奇数还是偶数）。
我认为 C 部分的技巧是在每一步否定
last值。 即0到0，1到2，2到1。I think Nathan Fellman is on the right track for part a and b (except b needs an extra piece of state: you need to keep track of if your digit position is odd or even).
I think the trick for part C is negating the
lastvalue at each step. I.e. 0 goes to 0, 1 goes to 2 and 2 goes to 1.