6

大きな10進数の2進数形式で1の数を調べようとしています（10進数は1000000まで大きくなる可能性があります）。

私はこのコードを試しました：

while(sum>0)  
{  
    if(sum%2 != 0)  
    {  
        c++;   // counting number of ones  
    }  
    sum=sum/2;  
}

10進数の入力が大きい場合は時間がかかるため、より高速なアルゴリズムが必要です。効率的なアルゴリズムを提案してください。

4

5 に答える 5

20

探しているのは「popcount」です。これは、後のx64 CPUに単一のCPU命令として実装されており、速度に勝るものはありません。

#ifdef __APPLE__
#define NAME(name) _##name
#else
#define NAME(name) name
#endif

/*
 * Count the number of bits set in the bitboard.
 *
 * %rdi: bb
 */
.globl NAME(cpuPopcount);
NAME(cpuPopcount):
    popcnt %rdi, %rax
    ret

ただし、もちろん、最初にCPUがサポートしていることをテストする必要があります。

/*
 * Test if the CPU has the popcnt instruction.
 */
.globl NAME(cpuHasPopcount);
NAME(cpuHasPopcount):
    pushq %rbx

    movl $1, %eax
    cpuid                   // ecx=feature info 1, edx=feature info 2

    xorl %eax, %eax

    testl $1 << 23, %ecx
    jz 1f
    movl $1, %eax

1:
    popq %rbx
    ret

Cでの実装は次のとおりです。

unsigned cppPopcount(unsigned bb)
{
#define C55 0x5555555555555555ULL
#define C33 0x3333333333333333ULL
#define C0F 0x0f0f0f0f0f0f0f0fULL
#define C01 0x0101010101010101ULL

    bb -= (bb >> 1) & C55;              // put count of each 2 bits into those 2 bits
    bb = (bb & C33) + ((bb >> 2) & C33);// put count of each 4 bits into those 4 bits
    bb = (bb + (bb >> 4)) & C0F;        // put count of each 8 bits into those 8 bits
    return (bb * C01) >> 56;            // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}

GNU Cコンパイラランタイムには、上記の実装よりも高速な「組み込み」が含まれています（CPU popcnt命令を使用する場合がありますが、これは実装固有です）。

unsigned builtinPopcount(unsigned bb)
{
    return __builtin_popcountll(bb);
}

ビットボードを使用して駒の位置を表す場合、ポップカウントがチェスの動きの生成に重要な役割を果たすため、上記のすべての実装がC++チェスライブラリで使用されます。ライブラリの初期化中に設定された関数ポインターを使用して、ユーザーが要求した実装をポイントし、そのポインターを介してpopcount関数を使用します。

興味深い問題であるため、Googleは他の多くの実装を提供します。例：http ：//wiki.cs.pdx.edu/forge/popcount.html 。

于 2013-02-04T08:10:40.573 に答える
19

C ++では、これを行うことができます。

#include <bitset>
#include <iostream>
#include <climits>

size_t popcount(size_t n) {
    std::bitset<sizeof(size_t) * CHAR_BIT> b(n);
    return b.count();
}

int main() {
    std::cout << popcount(1000000);
}
于 2013-02-04T08:16:30.320 に答える
12

多くの方法があります。ブライアン・カーニハンのやり方は、理解しやすく、非常に高速です。

unsigned int v = value(); // 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
}
于 2013-02-04T08:10:15.190 に答える
2

右ビットシフト演算子を使用

    int number = 15; // this is input number
    int oneCount = number & 1 ? 1 : 0;
    while(number = number >> 1)
    {
        if(number & 1)
            ++oneCount;
    }

    cout << "# of ones :"<< oneCount << endl;
于 2013-02-04T08:23:54.763 に答える
1 
int count_1s_in_Num(int num)
{
    int count=0;
    while(num!=0)
    {
        num = num & (num-1);
        count++;
    }
    return count;
}

AND演算を整数と減算の結果に適用すると、結果は、右端の1が0になることを除いて、元の整数と同じ新しい数値になります。たとえば、01110000 AND（01110000 – 1） =01110000および01101111=01100000。

このソリューションの実行時間はO（m）です。ここで、mはソリューション内の1の数です。

于 2014-12-17T18:13:38.750 に答える