language-agnostic - 检测整数中的单个一位流

Question

我必须检查一个数字是否满足以下条件:

• 在二进制中，所有一位必须是连续的。
• 数字必须至少设置一位。
• 连续的一位可能从 MSB 开始或在 LSB 结束，因此如果数字由单个一位流后跟一个零位流组成，则它是完全有效的，反之亦然。

我编写了一个代码来检查这些条件以解决现实世界的问题(检查数据文件完整性)。

它运行起来没有问题，而且时间紧迫，但我是个爱玩弄游戏的老怪人，喜欢这样的谜题，所以我想出了一个更聪明的方法来检查单人游戏-比特流。

字符串被零包围的情况很容易，但无法处理特殊情况。

欢迎任何想法、二进制 hack 和部分解决方案!

---

为了使我的要求更清楚一些示例:以下数字满足我的标准:

  0x80000000
  0x00000001
  0xff000000
  0x000000ff
  0xffffffff
  0x000ff000

以下数字没有(因为它们有不止一串连续的 1):

  0xf00000f <- one-bit streams should not wrap-around at 2^n
  0x0001700 <- a trivial example.
  0x0000000 <- no one bit at all.

Answer 1

这应该做你想做的。

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;