0

私はビットカウントについてさまざまな方法を勉強しています、または整数を与えられた人口カウント方法、この日の間、私は次のアルゴリズムがどのように機能するかを理解しようとしていました

pop(x)=-sum(x<<i)   where i=0:31

xの各値を計算した後、次のようになります。

x+2*x+4*x+8*x+16*x+..............+2^31*x  =4294967294*x

-1を掛けると得られます-4294967294*xが、ビット数はどのようにカウントされますか？この方法をよく理解するのを手伝ってください。ありがとう

4

2 に答える 2

6

私はあなたが意味すると信じています

$$ \ mathrm {pop}（x）=-\ sum_ {i = 0} ^ {31}（x \ overset {\ mathrm {rot}} {\ ll} i）$$

本の表紙に見られるように、Hacker's Delightの記号は、左シフトではなく左回転を意味し、間違った結果と反対票を生み出します。

この方法が機能するのは、ローテーションによってxのすべての2進数がすべての用語ですべての可能なビットに表示され、2の補数があるためです。

もっと簡単な例を見てみましょう。2進数が4桁しかない数値を考えてみましょう。この場合、数字はとして表すことができABCD、合計は次のことを意味します。

  ABCD  // x <<rot 0
+ BCDA  // x <<rot 1
+ CDAB  // x <<rot 2
+ DABC  // x <<rot 3

すべての列にA、B、C、Dがすべて含まれていることに注意してください。これは、ABCD実際には「2³A+2²B+2¹C+2⁰D」を意味するため、合計は次のようになります。

  2³ A        + 2² B        + 2¹ C        + 2⁰ D
+ 2³ B        + 2² C        + 2¹ D        + 2⁰ A
+ 2³ C        + 2² D        + 2¹ A        + 2⁰ B
+ 2³ D        + 2² A        + 2¹ B        + 2⁰ C
——————————————————————————————————————————————————————
= 2³(A+B+C+D) + 2²(B+C+D+A) + 2¹(C+D+A+B) + 2⁰(D+A+B+C)
= (2³ + 2² + 2¹ + 2⁰) × (A + B + C + D)

（A + B + C + D）はxの人口数であり、（2³+2²+2¹+2⁰）= 0b1111は2の補数で-1であるため、合計は人口数の負数になります。

引数は、32ビットの数値に簡単に拡張できます。

于 2012-03-22T16:19:00.530 に答える
0 
#include <stdio.h>
#include <conio.h>

unsigned int f (unsigned int a , unsigned int b);

unsigned int f (unsigned int a , unsigned int b)
{
   return a ?   f ( (a&b) << 1, a ^b) : b;
}

int bitcount(int n) {
    int tot = 0;

    int i;
    for (i = 1; i <= n; i = i<<1)
        if (n & i)
            ++tot;

    return tot;
}

int bitcount_sparse_ones(int n) {
    int tot = 0;

    while (n) {
        ++tot;
        n &= n - 1;
    }

    return tot;
}

int main()
{

int a = 12;
int b = 18;

int c = f(a,b);
printf("Sum = %d\n", c);

int  CountA = bitcount(a);
int  CountB = bitcount(b);

int CntA = bitcount_sparse_ones(a);
int CntB = bitcount_sparse_ones(b);

printf("CountA = %d and CountB = %d\n", CountA, CountB);
printf("CntA = %d and CntB = %d\n", CntA, CntB);
getch();

return 0;

}
于 2014-12-19T11:46:45.887 に答える