14

C ++で「ゼロ」ビットの数を見つけるにはどうすればよいですか. 整数があるとします。

int value = 276;

ビット 100010100 がありますが、ゼロをどのように数えますか?

4

13 に答える 13

26

効率が必要な場合は、本「Hackers Delight」に適切な実装があります。

22命令分岐フリー。

unsigned int count_1bits(unsigned int x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

unsigned int count_0bits(unsigned int x)
{
    return 32 - count_1bits(x);
}

それがどのように機能するかを説明しようと思います。これは分割統治アルゴリズムです。

(x >> 1) & 0x55555555

すべてのビットを 1 ステップ右にシフトし、すべてのビット ペアの最下位ビットを取得します。

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs)

したがって、基本的に、2 ビット順列すべての次の表が得られます。

1. (00 >> 1) & 01 = 00
2. (01 >> 1) & 01 = 00
3. (10 >> 1) & 01 = 01
4. (11 >> 1) & 01 = 01

x - ((x >> 1) & 0x55555555);

次に、シフトされていないペアからこれらを減算します。

1. 00 - 00 = 00 => 0 x 1 bits
2. 01 - 00 = 01 => 1 x 1 bits
3. 10 - 01 = 01 => 1 x 1 bits
4. 11 - 01 = 10 => 2 x 1 bits

x = x - ((x >> 1) & 0x55555555);

したがって、2ビットペアごとに変更したため、それらの値は対応する元の2ビットペアのビット数になります...そして、4ビットグループ、8ビットグループ、16ビットグループ、および最終的に同様の方法で続行します32ビット。

より良い説明が必要な場合は、本を購入してください。代替アルゴリズムなどの優れた説明と議論がたくさんあります...

于 2010-11-22T12:21:16.997 に答える
16

最も単純な最も簡単な方法は、ビットとカウントを反復処理することです。

size_t num_zeroes = 0;

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
  if ((value & (1 << i)) == 0)
    ++num_zeroes;
}

より良い (「より良い」のさまざまな値に対する) 方法はすべてありますが、これは非常に明確で、(コード的に) 非常に簡潔であり、多くのセットアップを必要としません。

改善と考えられるマイクロ最適化の 1 つは、マスクを計算して各ビットをテストするのではなく、値をシフトして常に右端のビットをテストすることです。

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
  if ((value & 1) == 0)
    ++num_zeroes;
}
于 2010-11-22T10:11:57.223 に答える
9

32 から設定されたビット数を引いた値を実行できます。

于 2010-11-22T10:14:38.393 に答える
8

GCC を使用している場合は、組み込み関数を試すことができます。

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)

詳細については、 GCC のドキュメントを参照してください。

于 2010-11-22T10:17:29.887 に答える
5

誰もこれについて言及していないことに驚いています：

int num_zero_bits = __builtin_popcount(~num);

numこれにより、GCC で使用した場合のゼロ ビットの数が得られます。

于 2016-07-19T20:58:27.393 に答える
4

セットビットを数えるカーニハンの方法

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

与えられたタスクに簡単に適応させることができます。ここでの反復回数は、設定されたビット数と同じです。

また、これや他のタイプのビット関連タスクを解決する他のさまざまな方法については、上記のリンクをお勧めします。マクロに実装されたビット数を取得する1行の例もあります。

于 2010-11-22T11:53:57.397 に答える
3

この種のことについては素晴らしい本があります: Hacker's Delight (ええ、名前は最低です: セキュリティとは何の関係もありません。「1」ビットをカウントするためのアルゴリズムがいくつか提供されていますが、最良のものはここでも見つけることができます(ただし、本にはこの Web サイトにない説明があります)。

「1」のビット数がわかったら、それを型表現のビット数から差し引くだけです。

于 2010-11-22T10:13:51.787 に答える
3

最も明白な解決策はルックアップ テーブルです。

/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }
于 2010-11-22T10:12:07.670 に答える
1

1の補数を実行してから、1を数えます。

count_zero_bits（x）= count_one_bits（〜x）;

1つを数えるコードを実装します。

template< typename I > 
int count_one_bits( I i )
{
   size_t numbits = 0;
   for( ; i != 0; i >>= 1 )
   {
      numbits += i&1;
   }
}

ただし、iが負の数の場合、関数に問題があります。これは、>>が右側に1ビットを配置するため、ループが終了しないためです。理想的な符号なし型を適用するためのテンプレート化された方法がある場合。

それができたら：

template< typename I > int count_zero_bits( I i )
{
   return count_one_bits( ~i );
}

動作します。

于 2010-11-22T10:31:37.043 に答える
0

私によると、正の整数でゼロのビット数を取得する最も簡単な方法は、次のコードです。

int get_zero_bit_count(int num)
{
    int cnt = 0;

    while(num > 0)
        {
            int and_num = num & 1;

            if (and_num != num) cnt++;

            num >>= 1; 
        }

        return cnt;
    }

このコードは理解しやすく、自己説明的です。これは、正の整数に対してうまく機能します。

于 2015-06-08T17:15:49.263 に答える