在不到n次的时间内在一个位串中找到两个连续的1？

Question

我试图找出一种方法来查看一个位串在比特串大小n中是否有少于n次的2个连续的.

例如,假设我们的字符串大小为5(索引0-4).如果索引1和3都是0,我可以返回false.但如果它们都是那些,那么我可能需要做5次才能找到答案.

bitstring不必是长度5.为简单起见,假设它可以在3到8之间.

Answer 1

最简单的解决方案可能是AND使用自身版本的原始字符串按位向左或向右移位1位.如果结果位串非零,那么你至少有一个11位:

test = (src & (src << 1));