的整数内检测单一比特流 [英] Detecting single one-bit streams within an integer

问题描述

我要检查一些是否满足以下条件：

• 在二进制，都是一个位必须是连续的。


• 的数目必须至少有一个比特组。


• 连续单位可能在MSB开始或在结束该LSB，因此，如果数量是由一个单一位流随后是零位流或反之亦然它是完全有效的。

我写了一个code，检查了这些条件，现实世界中的问题（检查数据文件的完整性）。

它的工作原理没有问题，它的任何东西，但时间紧迫的，但我是一个老位twiddeling怪胎爱这样的困惑，所以我试图用更巧妙的方法来检查单单想出了比特流。

若发现案件串由零包围很容易，但一个人不能用特殊的案件。

任何想法，二进制黑客和部分解决方案，欢迎！

---

为了使我的要求更加明确一些例子：下面的数满足我的标准：

 为0x80000000
  00000001
  0xff000000
  0x000000ff
  为0xffffffff
  0x000ff000
 

以下编号不（因为它们具有那些的多于一个连续字符串）：

  0xf00000f＆LT;  - 一个比特流应不环绕在2 ^ N
  0x0001700＆LT;  - 一个简单的例子。
  0x0000000＆LT;  - 没人上当的。
 

解决方案

这应该做你想要的。

 如果（我== 0）
    返回false;
而（I％2 == 0）{
    I = I / 2;
}
返回（I和第（i + 1））== 0;
 

I have to check a number if it satisfies the following criteria:

• in binary, all one-bits must be successive.
• the number must have at least one bit set.
• the successive one-bits may start at the MSB or end at the LSB, so it's perfectly valid if the number is made up of a single one-bit stream followed by a zero-bit stream or vice versa.

I wrote a code that checks for these conditions for a real-world problem (checking data-file integrity).

It works without problems and it's anything but time-critical, but I'm an old bit-twiddeling freak and love such puzzles, so I've tried to came up with a more clever way to check for single-one-bit streams.

Cases where the string is surrounded by zeros is easy, but that one can't deal with the special cases.

Any ideas, binary hacks and partial solutions are welcome!

---

To make my requirements more clear some examples: The following numbers satisfy my criteria:

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

The following numbers don't (as they have more than one successive string of ones):

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

解决方案

This should do what you want.

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

这篇关于的整数内检测单一比特流的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！