2

質問: 32 ビット整数の1すべてのセット ビット ( ) を右にシフトするアルゴリズムを開発する方法

例

V= 0b01001000110010

にVは 5 つのセット ビットが含まれており、それらを右にシフトすると、次のようになります。

V = 0b011111

私が試したこと：

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

上記のコードは、設定されたビット数を 32 ビット整数で返します。

そして次のコードで

c = (1<<c) - 1;

c最初のビットを に設定します1。説明

上記のソリューションよりも優れたアルゴリズムは他にありますか?

提案されたソリューションでビット演算 ( &、|、^、~、 ) のみを使用することは可能ですか?>><<

4

8 に答える 8

7 
bitset<32> const bv( V );
size_t const numSetBits = bv.count();
uint32_t const answer = ~( ~0U << numSetBits );
于 2013-04-14T21:01:27.623 に答える
4

私が見る最善の解決策は、人口カウントを使用して 1 ビットの数を取得し、(1 << (pop_cnt % typeSize)) - 1[1] を使用することです。これは既に行っていることです。

ここで見ることができる人口数を見つけるには、いくつかの効率的な実装があります。__builtin_popcountgcc に問題がなければ、ハードウェアに最も効率的なコードを生成するgcc の組み込み命令があります。

[1] 別の投稿のコメントで正しく指摘されているよう1 << pop_cntに、単語内のすべてのビットが 1 に設定されている場合の動作は未定義です。これを回避するには、事前に modulo wordsize を適用してください。符号なしの型を使用している限り、これにより未定義の動作が回避され、正しい結果が得られ、ワードサイズのデータ​​型を使用する場合、実際には x86 でまったく同じコードが生成されるはずです。

于 2013-04-14T21:16:41.720 に答える
0

これは、いくつかの値に対してそれを行いますv。

// Count the bits (only iterates once per set bit)
unsigned count = 0;
for(; v!=0; v&=(v-1))
    ++count;

// Produce that many "shifted bits".
v = (1 << count) - 1;
于 2013-04-14T21:02:45.050 に答える
0

2 つの変数を使用することをお勧めします。 

unsigned int Squish_Bits(unsigned int value)
{
  unsigned int result = 0;
  for (i = 0; i < sizeof(value)/CHAR_BITS; ++i)
  {
    if (value & (1 << i))
    {
       result <<= 1;
       result |= 1;
    }
  }
  return result;
}

この関数はビットをカウントしませんが、例を解決します。

これは、ビットをキャリーにシフトしてからキャリーを結果にシフトできるため、アセンブリ言語で実装する方が適切です。

于 2013-04-14T21:04:18.140 に答える
0

使えますV >>= 1;か、int v = (V >> 1);使えませんか？

意図がすべての非ゼロビットを右端までシフトすることである場合、次のようにすることができます...

int v = 0;
int i;

for( i = 0; i < 32; i++, V >>= 1 )
   if( (V & 1) != 0 )
      v = (v << 1) + 1;

V = v;
于 2013-04-14T20:54:36.637 に答える
0

魔法の定数を見つけて、(32 - 5) で乗算と右シフトを使用することができます (32 ビット整数を使用して定数を格納すると仮定します)。

#include <iostream>

int main()
{
   unsigned V = 0b01001000110010; 
   unsigned magic = 0x79838cb2; // try some random numbers until you succeed
   unsigned result = (V * magic) >> (32 - 5);   

   std::cout << result; // writes 31
}

そのような定数を見つける方法については、この質問を見てください

于 2013-04-14T21:00:14.030 に答える
0 
int shift(int V) {
    if (V != 0) {
        int r = 1;
        for (int i = 0; i < 32; i++)
            if ((V >> i) & 1) r <<= 1;
        return r - 1;
    } else return 0;
}

いくつかの追加を保存します。

于 2013-04-14T21:25:27.270 に答える
0 
int v = 0b01001000110010;
int a = 0;

for (int i = 0; i < 32; ++i) {
    if((v & 1) == 1)
       a = (a << 1) + 1;

    v = v >> 1;
}

v = a;
于 2013-04-14T21:05:57.557 に答える