2

次の基準を満たしているかどうかを確認する必要があります。

  • バイナリでは、すべての1ビットが連続している必要があります。
  • 番号には少なくとも1つのビットが設定されている必要があります。
  • 連続する1ビットはMSBで開始するか、LSBで終了する可能性があるため、数値が単一の1ビットストリームとそれに続くゼロビットストリームで構成されている場合、またはその逆の場合は完全に有効です。

実際の問題についてこれらの条件をチェックする（データファイルの整合性をチェックする）コードを作成しました。

それは問題なく動作し、タイムクリティカルではありませんが、私は古いビットをいじくり回すフリークであり、そのようなパズルが大好きなので、シングル1ビットストリームをチェックするためのより賢い方法を考え出しました。

文字列がゼロで囲まれている場合は簡単ですが、特殊な場合には対応できません。

どんなアイデア、バイナリハック、部分的な解決策も大歓迎です！

要件をより明確にするために、いくつかの例を示します。次の数値は私の基準を満たしています。

  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

そこでほぼ同じ問題を解決しましたhttp://smallissimo.blogspot.fr/2012/04/meteor-contest-part-3-reducing.htmlメソッド hasInsetZero: (および他のいくつかのビットトリックを使用)

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. 結果が 2 の累乗でゼロでない場合、成功です。

これらの操作はすべて、次のように O(1) または O(log(整数ビット幅)) のいずれかです。

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になります）。

MSN

于 2009-01-20T19:23:49.223 に答える
1

bsr と bsf を使用して、数値に設定された最小ビットと最大ビットを決定します。そこから、基準を満たす有効な数値を作成します。既知の有効な数値と実際の数値を比較して等しいかどうかを確認します。ループはなく、比較は 1 つだけです。

疑似コード:

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 に答える