稀疏二值分解

Question

如果非负整数 N 的二进制表示不包含两个连续设置为 1 的位，则称为稀疏整数。例如，41 是稀疏的，因为其二进制表示为“101001”并且不包含两个连续的 1。另一方面，26 并不稀疏，因为它的二进制表示是“11010”并且包含两个连续的 1。

\n

如果 P 和 Q 是稀疏的且 N = P + Q，则两个非负整数 P 和 Q 称为整数 N 的稀疏分解。

\n

例如：

\n

8 and 18 are a sparse decomposition of 26 (binary representation of 8 is "1000", binary representation of 18 is "10010");\n9 and 17 are a sparse decomposition of 26 (binary representation of 9 is "1001", binary representation of 17 is "10001");\n2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is "11000", which is not sparse.\n\n

\n

我需要一个函数，给定一个非负整数 N，返回作为 N 稀疏分解一部分的任何整数。如果 N 没有稀疏分解，该函数应返回 \xe2\x88\x921 。

\n

例如，给定 N = 26，该函数可能返回 8、9、17 或 18，如上面示例中所述。N = 26 的所有其他可能结果为 5、10、16 和 21。

\n

\n
• 我尝试了这个：当 N=26, 1166, 1031 时有效。但是 id 不适用于非常大的数字，例如74901729由于运行时错误（超时）
\n

\n

\nimport re\ndef solution(N):\n\n    for i in range(N):\n        x = N-i\n        is_x_sparse = not re.findall('11+', bin(x))\n        is_i_sparse = not re.findall('11+', bin(i))\n        if is_x_sparse and is_i_sparse:\n            return i\n

\n

Answer 1

根据我的评论，any 的一个解决方案x是pair (x & 0x55555555, x & 0xAAAAAAAA)，您可以返回其中两个元素中的任何一个。

现在，为什么这会起作用？让我们看看二进制的掩码：

0x55555555 = 0b01010101010101010101010101010101
0xAAAAAAAA = 0b10101010101010101010101010101010

它们都有交替的 1 和 0，因此任何具有其中一个掩码的数字的按位与结果永远不会有两个连续的 1。

唯一缺少的是这两个值的总和是否等于原始值x。情况确实如此：x设置的每一位都1将恰好位于两项中的一项中，并且在加法过程中不会生成进位（求和时，我们永远不会对两个 1 求和）。因此，加法简化为操作数的二进制或，结果将是原始的x。

最后一点，我提到的掩码是 32 位的，但可以通过扩展或缩小相同的模式来适应任何宽度。