c++ - 连续位的长度 1 流后跟 0

Question

是面试问题，所以寻找可能不是显而易见的解决方案。

假设有 1111...111100000...000 的大流

找到 1 的长度(数字)。

您可以假设这里的 1 是一个设置位。

如果 1 是符号，它将如何变化，比如 aaa..aaaabbbb...bbbbb

我可以提出的一个解决方案是查看第一个位/符号，然后继续将间隔加倍，然后查看第 3 个，然后第 7 个，依此类推。当你击中 0 或其他符号时，然后再次使用分而治之的方式回到最后一个位置。

Answer 1

如果您可以随机访问流并且流的长度已知，则可以使用 O(log n) 中的二进制搜索变体来实现。

或者，您可以使用 0x1 &，如果为零，则递增计数器并右移 1。或者，您可以检查整个字节(字、双字、四字等)是否非零以更快地找到那些开始的街区。无论哪种方式，都是 O(n)。