二进制字符串余数 3

Question

-当 x 是二进制数时如何找到 x mod 3？不允许使用转换为十进制然后使用 % 运算符。

-eg- 如果 x 是 1101 那么输出应该是 1 但不要将 1101 转换为 13 然后通过 % 3 找到

Answer 1

既然你说“字符串”，我将添加以下技术：

0请注意，如果在二进制数末尾附加，则其值将加倍。1如果在末尾追加，则将其加倍并加 1。

也就是说，如果您已经处理了直到某个数字的所有数字（称这个数字到那个数字a），并且您知道a % 3 = x对于某些x=1, 2 or 0，那么您可以告诉以下内容：

a0 % 3 = (2 * a) % 3 = ((2 % 3) * (a % 3)) % 3 = (2 * (a % 3)) % 3
a1 % 3 = (2 * a + 1) % 3 = ((2 % 3) * (a % 3) + (1 % 3)) % 3 = (2 * (a % 3) + 1) % 3

这样，您就可以轻松做出以下区分：

Current mod | Next digit | New mod
------------+------------+---------
   0            0            0
   0            1            1
   1            0            2
   1            1            0
   2            0            1
   2            1            2

也就是说，您可以从左到右遍历字符串（假设 msbf 表示法）并new mod根据表更新。你从 开始current mod = 0。