编写代码来确定一个数字是否能被 3 整除。该函数的输入是single位，0 或 1，如果到目前为止收到的数字是可被 3 整除的数字的二进制表示形式，则输出应为 1，否则为 0。
例子：
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
这是基于一个面试问题。我要求绘制逻辑门，但由于这是 stackoverflow，我会接受任何编码语言。硬件实现（verilog 等）的奖励积分。
A 部分（简单）：第一个输入是 MSB。
b部分（稍微难一点）：第一个输入是 LSB。
c部分（困难）：(a) 和 (b) 哪一个更快、更小？ （理论上不是 Big-O 意义上的，但实际上更快/更小。）现在采用较慢/较大的那个，使其与更快/较小的那个一样快/小。
有一个相当著名的技巧，可以通过交替加减十进制数字来确定一个数字是否是 11 的倍数。如果最后得到的数字是 11 的倍数，那么一开始的数字也是 11 的倍数：
47278 4 - 7 + 2 - 7 + 8 = 0, multiple of 11 (47278 = 11 * 4298)
52214 5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)
我们可以将同样的技巧应用于二进制数。二进制数是 3 的倍数当且仅当其位的交替和也是 3 的倍数时：
4 = 100 1 - 0 + 0 = 1, not multiple of 3
6 = 110 1 - 1 + 0 = 0, multiple of 3
78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3
109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3
无论从 MSB 还是 LSB 开始都没有区别，因此以下 Python 函数在这两种情况下都同样有效。它需要一个每次返回一位的迭代器。multiplier在 1 和 2 之间交替，而不是在 1 和 -1 之间交替，以避免取负数的模。
def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
