2

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

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

我编写了一个代码来检查这些条件是否存在实际问题（检查数据文件完整性）。

它可以正常工作，而且时间紧迫，但我是一个老顽固的怪胎，喜欢这样的谜题，所以我试图想出一种更聪明的方法来检查单比特流。

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

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

为了让我的要求更清楚一些例子：以下数字满足我的标准：

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

以下数字没有（因为它们有多个连续的一串）：

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

7 回答 7

3 
bool isOK(uint val) {
   while (val != 0 && (val & 1u) == 0) val >>= 1;
   if (val == 0) return false;
   while (val != 0 && (val & 1u) == 1) val >>= 1;
   return val == 0;
}

; x86 assembly
mov eax, THE_NUMBER ; store the number in eax
bsf ecx, eax
jz .notok
mov edi, 1
shl edi, cl
mov esi, eax
add esi, edi
test esi, eax
jnz .notok
mov eax, 1
jmp .end
.notok:
mov eax, 0
.end: ; eax = 1 if satisfies the criteria, otherwise it's 0
于 2009-01-20T19:06:46.217 回答
3

这应该做你想要的。

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;
于 2009-01-20T19:06:56.823 回答
2

我在方法 hasInsetZero 中解决了几乎相同的问题http://smallissimo.blogspot.fr/2012/04/meteor-contest-part-3-reducing.html：（并使用了其他一些技巧）

hasInsetZero: aMask
    | allOnes |
    allOnes := aMask bitOr: aMask - 1.
    ^(allOnes bitAnd: allOnes + 1) > 0

它是 Smalltalk 代码，但用 C 语言翻译（我们需要否定并关心 0），即：

int all_set_bits_are_consecutive( x )
/* return non zero if at least one bit is set, and all set bits are consecutives */
{
   int y = x | (x-1);
   return x && (! (y & (y+1)));
}
于 2012-06-29T01:09:07.130 回答
1

假设您想要快速，基本算法将是：

  1. 找到最低位集。
  2. 按最低位集的索引移动数字。
  3. 添加1。
  4. 如果 result 是 2 且非零的幂，则成功！

所有这些操作都是 O(1) 或 O(log(integer bit width))，如下所示：

unsigned int lowest_power_of_2(unsigned int value) 
{ return value & -value; }

unsigned int count_bits_set(unsigned int value) 
{ /* see counting bits set in parallel */ }

unsigned int lowest_bit_set_or_overflow_if_zero(unsigned int value)
{ return count_bits_set(lowest_power_of_2(value) - 1); }

unsigned int is_zero_or_power_of_2(unsigned int value)
{ return value && (value & (value - 1))==0; }

bool magic_function(unsigned in value)
{ return is_zero_or_power_of_2((value >> (lowest_bit_set_or_overflow_if_zero(lowest_power_of_2(value)))) + 1); }

编辑：更新最终操作以占零，但 OP 的算法要快得多，因为它都是恒定操作（尽管考虑溢出将是 PITA）。

微信

于 2009-01-20T19:23:49.223 回答
1

我会使用 bsr 和 bsf 来确定数字中设置的最小和最大位。由此，创建一个满足条件的有效数字。比较已知的有效数字与实际数字是否相等。没有循环，只有一个比较。

伪代码：

min_bit = bsf(number);
max_bit = bsr(number);
valid_number = ~(-1 << (max_bit - min_bit) ) << min_bit;
return ( number == valid_number );
于 2009-01-20T19:28:21.850 回答
1

我的正在进行中的版本。不作为答案，只是为了提供更多想法并记录我目前的方法：

int IsSingleBitStream (unsigned int a)
{
  // isolate lowest bit:
  unsigned int lowest_bit = a & (a-1);

  // add lowest bit to number. If our number is a single bit string, this will
  // result in an integer with only a single bit set because the addition will     
  // propagate up the the highest bit. We ought to end up with a power of two.
  a += lowest_bit;

  // check if result is a power of two:
  return (!a || !(a & (a - 1)));
}

如果以下行，此代码将不起作用：

a+= 最低位

溢出。此外，如果有多个位域，我不确定我的“隔离单个位”代码是否有效。

于 2009-01-20T19:36:40.897 回答
0

(N^2 - N) / 2N 位整数有可能（32 位为 496）。

您可以使用查找表。

于 2009-01-20T19:09:11.577 回答