algorithm - 二进制串余数 3

Question

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

-例如-如果 x 是 1101 那么输出应该是 1 但不要将 1101 转换为 13 然后按 % 3 求

Answer 1

既然你说的是“字符串”，我就添加以下技巧:

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

也就是说，如果您已经处理了直到某个数字的所有数字(将此数字称为该数字 a)，并且您知道 a % 3 = x 对于某些 x=1、2 或 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 开始。