检查一个数字是否可以被3整除

Question

编写代码以确定数字是否可被3整除.函数的输入是单个位,0或1,如果到目前为止接收的数字是可被3整除的数字的二进制表示,则输出应为1,否则零.

例子:

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意义上的,但实际上更快/更小.)现在采用较慢/较大的一个,并使其快/小与更快/更小的一个.

Answer 1

通过交替地加上和减去其十进制数字,确定一个数是否是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

Answer 2

这里......新的东西...如何检查任何长度(甚至数千个数字)的二进制数是否可以被3整除.

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

从图片.

1. 你从双圈开始.
2. 当你得到一个或零时,如果数字在圆圈内,那么你留在那个圆圈里.但是,如果数字在一条线上,那么您将越过该线.
3. 重复步骤2,直到所有数字都被填充.
4. 如果你最终以双圈结束,那么二进制数可以被3整除.

您也可以使用它来生成可被3整除的数字.我不会想象将它转换成电路很难.

1使用图表的例子......

11000000000001011111111111101可被3整除(再次以双圈结束)

亲自试试吧.

您还可以执行类似的操作来执行MOD 10,用于将二进制数转换为基数为10的数字.(10个圆圈,每个圆圈加倍圈出并表示模数得到的值0到9)

编辑:这是从左到右运行的数字,虽然修改有限状态机接受反向语言并不困难.

注意:在图形的ASCII表示中()表示单个圆,(())表示双圆.在有限状态机中,这些被称为状态,双圆是接受状态(意味着它最终可被3整除的状态)

Answer 3

嘿

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

说明:0可被3整除.0 << 1 + 0 = 0.重复使用S = (S << 1 + I) % 3和O = 1if S == 0.

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

说明:0可被3整除.0 >> 1 + 0 = 0.重复使用S = (S >> 1 + I) % 3和O = 1if S == 0.

S'与上面不同,但O的作用相同,因为S'对于相同的情况(00和11)是0.由于在两种情况下O都相同,O_LSB = O_MSB,因此要使MSB与LSB一样短,反之亦然,只需使用两者中最短的.

Answer 4

这是一种简单的手工操作方法.由于1 = 2 ² mod 3,对于每个正整数,我们得到1 = 2 ²ⁿ mod 3.此外,2 = 2 ^{2n + 1} mod 3.因此可以通过计算奇数位位置的1位来确定整数是否可被3整除,将该数乘以2,在偶数位加上1位数加上它们到结果并检查结果是否可被3整除.

示例:57 ₁₀ = 111001 ₂.奇数位有2位,偶数位有2位.2*2 + 2 = 6可被3整除.因此57可被3整除.

这也是解决问题c)的想法.如果一个反转二进制整数的位顺序,则所有位保持在偶数/奇数位置或所有位都改变.因此,反转整数n的位的顺序结果是一个整数,当且仅当n可被3整除时,该整数可被3整除.因此问题a)的任何解决方案都可以在不改变问题b)的情况下工作,反之亦然.嗯,也许这有助于弄清楚哪种方法更快......

Answer 5

您需要使用算术模3进行所有计算.这就是方法

MSB:

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

LSB:

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

这是一般的想法......

现在,您的部分是了解为什么这是正确的.

是的,自己做功课;)