2

bitCount()ファイルに名前が付けられた関数を記述したいと思います。この関数bitcount.cは、符号なし整数引数のバイナリ表現のビット数を返します。

これが私がこれまでに持っているものです：

#include <stdio.h>

int bitCount (unsigned int n);

int main () {
    printf ("# 1-bits in base 2 representation of %u = %d, should be 0\n",
        0, bitCount (0));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        1, bitCount (1));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 16\n",
        2863311530u, bitCount (2863311530u));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        536870912, bitCount (536870912));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 32\n",
        4294967295u, bitCount (4294967295u));
    return 0;
}

int bitCount (unsigned int n) {
    /* your code here */
}

さて、これを実行すると、次のようになります。

# 1-bits in base 2 representation of 0 = 1, should be 0
# 1-bits in base 2 representation of 1 = 56, should be 1
# 1-bits in base 2 representation of 2863311530 = 57, should be 16
# 1-bits in base 2 representation of 536870912 = 67, should be 1
# 1-bits in base 2 representation of 4294967295 = 65, should be 32

RUN SUCCESSFUL (total time: 14ms)

正しいビット数を返しません。

Cの符号なし整数引数のバイナリ表現のビット数を返すための最良の方法は何ですか？

4

3 に答える 3

11

これは、繰り返す必要のないソリューションです。バイナリにビットを追加することはビットの位置に完全に依存せず、合計が2ビットを超えることはないという事実を利用しています。00+00=00、、、、。00+01=01_ 01+00=01_ 01+01=10最初の加算は16個の異なる1ビット値を同時に加算し、2番目の加算は8個の2ビット値を加算し、その後、値が1つだけになるまで、それぞれが半分の数を加算します。

int bitCount(unsigned int n)
{
    n = ((0xaaaaaaaa & n) >> 1) + (0x55555555 & n);
    n = ((0xcccccccc & n) >> 2) + (0x33333333 & n);
    n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n);
    n = ((0xff00ff00 & n) >> 8) + (0x00ff00ff & n);
    n = ((0xffff0000 & n) >> 16) + (0x0000ffff & n);
    return n;
}

これは32ビット整数にハードコーディングされています。サイズが異なる場合は、調整する必要があります。

于 2014-11-21T21:35:33.523 に答える
10 
 int bitCount(unsigned int n) {

    int counter = 0;
    while(n) {
        counter += n % 2;
        n >>= 1;
    }
    return counter;
 }
于 2013-02-08T20:45:54.363 に答える
5

ここで答えられているように、これを計算するためのかなり洗練された方法がいくつかあることがわかりました。

次のimpl（私はずっと前に学んだ）は、各反復で最下位ビットをノックオフするループを単純に実行します。

int bitCount(unsigned int n) {

  int counter = 0;
  while(n) {
    counter ++;
    n &= (n - 1);
  }
  return counter;
}
于 2013-07-17T18:51:24.040 に答える