Làm cách nào để đếm số bit đã đặt trong số nguyên 32 bit?

898
Matt Howells 2008-09-21 09:04.

8 bit đại diện cho số 7 trông như thế này:

00000111

Ba bit được thiết lập.

Thuật toán xác định số bit đặt trong số nguyên 32 bit là gì?

30 answers

879
Peter Cordes 2008-09-21 09:05.

Điều này được gọi là ' Hamming Weight ', 'popcount' hoặc 'bổ sung sang một bên'.

Thuật toán 'tốt nhất' thực sự phụ thuộc vào CPU bạn đang sử dụng và kiểu sử dụng của bạn là gì.

Một số CPU có một lệnh tích hợp duy nhất để thực hiện việc đó và những CPU khác có các lệnh song song hoạt động trên các vectơ bit. Các hướng dẫn song song (như x86 popcnt, trên các CPU được hỗ trợ) gần như chắc chắn sẽ nhanh nhất. Một số kiến ​​trúc khác có thể có một lệnh chậm được triển khai với một vòng lặp vi mã kiểm tra một bit mỗi chu kỳ ( cần trích dẫn ).

Phương pháp tra cứu bảng được điền sẵn có thể rất nhanh nếu CPU của bạn có bộ nhớ cache lớn và / hoặc bạn đang thực hiện nhiều hướng dẫn này trong một vòng lặp chặt chẽ. Tuy nhiên, nó có thể bị ảnh hưởng vì chi phí của một "bộ nhớ cache", nơi CPU phải tìm nạp một số bảng từ bộ nhớ chính. (Tra cứu từng byte riêng biệt để giữ cho bảng nhỏ.)

Nếu bạn biết rằng các byte của bạn chủ yếu là 0 hoặc chủ yếu là 1 thì có các thuật toán rất hiệu quả cho các trường hợp này.

Tôi tin rằng một thuật toán có mục đích chung rất tốt là thuật toán sau, được gọi là 'song song' hoặc 'thuật toán SWAR có độ chính xác thay đổi'. Tôi đã diễn đạt điều này bằng một ngôn ngữ giả giống C, bạn có thể cần phải điều chỉnh nó để hoạt động cho một ngôn ngữ cụ thể (ví dụ: sử dụng uint32_t cho C ++ và >>> trong Java):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Đối với JavaScript: ép buộc thành số nguyên với |0cho hiệu suất: thay đổi dòng đầu tiên thànhi = (i|0) - ((i >> 1) & 0x55555555);

Điều này có hành vi tốt nhất trong trường hợp xấu nhất của bất kỳ thuật toán nào được thảo luận, vì vậy sẽ đối phó hiệu quả với bất kỳ kiểu sử dụng hoặc giá trị nào bạn ném vào nó.

Người giới thiệu:

  • https://graphics.stanford.edu/~seander/bithacks.html
  • https://en.wikipedia.org/wiki/Hamming_weight
  • http://gurmeet.net/puzzles/fast-bit-counting-routines/
  • http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)

Cách hoạt động của bithack SWAR này:

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

Bước đầu tiên là một phiên bản tối ưu hóa của mặt nạ để cô lập các bit lẻ / chẵn, chuyển sang dòng chúng và thêm vào. Điều này thực hiện hiệu quả 16 phép bổ sung riêng biệt trong bộ tích lũy 2 bit ( SWAR = SIMD trong thanh ghi ). Giống như (i & 0x55555555) + ((i>>1) & 0x55555555).

Bước tiếp theo lấy lẻ / chẵn tám trong số các bộ tích lũy 16x 2 bit đó và cộng lại, tạo ra tổng 8x 4 bit. Lần i - ...này không thể tối ưu hóa nên nó chỉ che khuất trước / sau khi chuyển đổi. Sử dụng cùng một 0x33...hằng số cả hai lần thay vì 0xccc...trước khi dịch chuyển là một điều tốt khi biên dịch cho các ISA cần xây dựng các hằng số 32-bit trong các thanh ghi một cách riêng biệt.

Bước chuyển và bổ sung cuối cùng (i + (i >> 4)) & 0x0F0F0F0Fmở rộng thành 4x bộ tích lũy 8 bit. Nó che dấu sau khi thêm thay vì trước đó, vì giá trị lớn nhất trong bất kỳ bộ tích lũy 4 bit nào là 4, nếu tất cả 4 bit của các bit đầu vào tương ứng đã được đặt. 4 + 4 = 8 mà vẫn phù hợp với 4 bit, vì vậy việc mang giữa các phần tử nibble là không thể i + (i >> 4).

Cho đến nay, đây chỉ là SIMD khá bình thường sử dụng các kỹ thuật SWAR với một vài tối ưu hóa thông minh. Tiếp tục với cùng một mẫu cho 2 bước nữa có thể mở rộng thành 2x 16 bit rồi đến 1x 32 bit. Nhưng có một cách hiệu quả hơn trên các máy có phần cứng nhanh gấp bội:

Khi chúng ta có đủ "phần tử", một phép nhân với hằng số ma thuật có thể tổng tất cả các phần tử thành phần tử hàng đầu . Trong trường hợp này là các phần tử byte. Phép nhân được thực hiện bằng cách chuyển sang trái và cộng, do đó, một phép nhân có x * 0x01010101kết quả x + (x<<8) + (x<<16) + (x<<24). Yếu tố 8-bit của chúng tôi là đủ rộng (và giữ số lượng đủ nhỏ) rằng điều này không sản xuất carry vào đầu mà 8 bit.

Phiên bản 64-bit của điều này có thể tạo 8 phần tử 8-bit trong một số nguyên 64-bit với hệ số nhân 0x0101010101010101 và trích xuất byte cao với >>56. Vì vậy, nó không cần thêm bất kỳ bước nào, chỉ cần các hằng số rộng hơn. Đây là những gì GCC sử dụng cho __builtin_popcountllcác hệ thống x86 khi popcnthướng dẫn phần cứng không được kích hoạt. Nếu bạn có thể sử dụng nội trang hoặc nội dung cho việc này, hãy làm như vậy để trình biên dịch có cơ hội thực hiện tối ưu hóa mục tiêu cụ thể.


Với SIMD đầy đủ cho các vectơ rộng hơn (ví dụ: đếm toàn bộ mảng)

Thuật toán bitwise-SWAR này có thể song song được thực hiện trong nhiều phần tử vectơ cùng một lúc, thay vì trong một thanh ghi số nguyên duy nhất, để tăng tốc độ trên các CPU có SIMD nhưng không có lệnh popcount sử dụng được. (ví dụ: mã x86-64 phải chạy trên bất kỳ CPU nào, không chỉ Nehalem trở lên.)

Tuy nhiên, cách tốt nhất để sử dụng hướng dẫn vectơ cho popcount thường là sử dụng một biến trộn để thực hiện tra cứu bảng cho 4 bit tại một thời điểm của mỗi byte song song. (4 bit chỉ mục một bảng 16 mục được giữ trong một thanh ghi vectơ).

Trên CPU Intel, lệnh popcnt 64 bit của phần cứng có thể vượt trội hơn cách triển khai song song bit SSSE3PSHUFB khoảng hệ số 2, nhưng chỉ khi trình biên dịch của bạn làm đúng . Nếu không, SSE có thể đi trước đáng kể. Các phiên bản trình biên dịch mới hơn đã biết về vấn đề phụ thuộc sai popcnt vào Intel .

  • https://github.com/WojciechMula/sse-popcounttài khoản SIMD x86 hiện đại dành cho SSSE3, AVX2, AVX512BW, AVX512VBMI hoặc AVX512 VPOPCNT. Sử dụng Harley-Seal trên các vectơ để trì hoãn popcount trong một phần tử. (Còn ARM NEON)
  • Đếm 1 bit (số lượng dân số) trên dữ liệu lớn bằng AVX-512 hoặc AVX-2
  • liên quan: https://github.com/mklarqvist/positional-popcount- số đếm riêng biệt cho từng vị trí bit của nhiều số nguyên 8, 16, 32 hoặc 64 bit. (Một lần nữa, x86 SIMD bao gồm AVX-512 thực sự tốt trong việc này, với vpternlogdviệc tạo ra Harley-Seal rất tốt.)
219
Peter Cordes 2008-09-21 09:23.

Cũng xem xét các chức năng tích hợp của trình biên dịch của bạn.

Ví dụ, trên trình biên dịch GNU, bạn chỉ có thể sử dụng:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

Trong trường hợp xấu nhất, trình biên dịch sẽ tạo ra một lệnh gọi đến một hàm. Trong trường hợp tốt nhất, trình biên dịch sẽ phát ra lệnh cpu để thực hiện công việc tương tự nhanh hơn.

Bản chất của GCC thậm chí còn hoạt động trên nhiều nền tảng. Popcount sẽ trở thành xu hướng chủ đạo trong kiến ​​trúc x86, vì vậy việc bắt đầu sử dụng nội tại ngay bây giờ là rất hợp lý. Các kiến ​​trúc khác có số lượng lớn trong nhiều năm.


Trên x86, bạn có thể nói với trình biên dịch rằng nó có thể giả định hỗ trợ cho popcntlệnh bằng -mpopcnthoặc -msse4.2cũng cho phép các lệnh vectơ đã được thêm vào trong cùng một thế hệ. Xem các tùy chọn GCC x86 . -march=nehalem(hoặc -march=bất kỳ CPU nào bạn muốn mã của mình giả sử và điều chỉnh) có thể là một lựa chọn tốt. Chạy tệp nhị phân kết quả trên một CPU cũ hơn sẽ dẫn đến lỗi lệnh bất hợp pháp.

Để làm cho mã nhị phân được tối ưu hóa cho máy bạn xây dựng chúng, hãy sử dụng -march=native(với gcc, clang hoặc ICC).

MSVC cung cấp một nội tại cho x86 popcnthướng dẫn , nhưng không giống như gcc nó thực sự là một bên trong thành hướng dẫn phần cứng và yêu cầu hỗ trợ phần cứng.


Sử dụng std::bitset<>::count()thay vì cài sẵn

Về lý thuyết, bất kỳ trình biên dịch nào biết cách bật số lượng hiệu quả cho CPU mục tiêu sẽ thể hiện chức năng đó thông qua ISO C ++ std::bitset<>. Trong thực tế, bạn có thể tốt hơn với bit-hack AND / shift / ADD trong một số trường hợp đối với một số CPU mục tiêu.

Đối với các kiến ​​trúc đích trong đó popcount phần cứng là một phần mở rộng tùy chọn (như x86), không phải tất cả các trình biên dịch đều std::bitsetcó lợi thế của nó khi có sẵn. Ví dụ: MSVC không có cách nào để kích hoạt popcnthỗ trợ tại thời điểm biên dịch và luôn sử dụng tra cứu bảng , ngay cả với /Ox /arch:AVX(ngụ ý SSE4.2, mặc dù về mặt kỹ thuật có một bit tính năng riêng cho popcnt.)

Nhưng ít nhất bạn có được thứ gì đó có thể di động hoạt động ở mọi nơi và với gcc / clang với các tùy chọn mục tiêu phù hợp, bạn sẽ nhận được tài khoản phần cứng cho các kiến ​​trúc hỗ trợ nó.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Xem asm từ gcc, clang, icc và MSVC trên trình khám phá trình biên dịch Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcntphát ra cái này:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11phát ra (đối với intphiên bản đối số):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

Nguồn này không dành riêng cho x86 hoặc dành riêng cho GNU, nhưng chỉ biên dịch tốt cho x86 với gcc / clang / icc.

Cũng lưu ý rằng dự phòng của gcc cho các kiến ​​trúc không có cửa sổ bật chỉ lệnh đơn là tra cứu bảng theo từng byte. Ví dụ, điều này không tuyệt vời đối với ARM .

194
paxdiablo 2008-09-21 15:14.

Theo tôi, giải pháp "tốt nhất" là giải pháp có thể được đọc bởi một lập trình viên khác (hoặc lập trình viên ban đầu hai năm sau đó) mà không có nhiều bình luận. Bạn cũng có thể muốn giải pháp nhanh nhất hoặc thông minh nhất mà một số đã cung cấp nhưng tôi thích khả năng đọc hơn sự thông minh bất cứ lúc nào.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

Nếu bạn muốn tốc độ cao hơn (và giả sử bạn ghi chép nó tốt để giúp đỡ những người kế nhiệm), bạn có thể sử dụng tra cứu bảng:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

Mặc dù những kích thước này dựa trên kích thước loại dữ liệu cụ thể nên chúng không có tính di động. Tuy nhiên, vì dù sao đi nữa, nhiều tính năng tối ưu hóa hiệu suất không thể di động, nên đó có thể không phải là vấn đề. Nếu bạn muốn tính di động, tôi sẽ gắn bó với giải pháp có thể đọc được.

98
Kevin Little 2008-09-21 09:38.

Từ Hacker's Delight, p. 66, Hình 5-2

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

Thực hiện trong các lệnh ~ 20-ish (phụ thuộc vào vòm), không phân nhánh.

Delight của hacker thú vị! Rất khuyến khích.

76
vidit 2013-04-13 09:14.

Tôi nghĩ cách nhanh nhất — mà không cần sử dụng bảng tra cứu và popcount — là cách sau. Nó đếm các bit đã đặt chỉ với 12 phép toán.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Nó hoạt động vì bạn có thể đếm tổng số bit đặt bằng cách chia làm hai nửa, đếm số bit đặt ở cả hai nửa và sau đó cộng chúng lại. Hay còn gọi là Divide and Conquermô hình. Hãy đi vào chi tiết ..

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

Số bit trong hai bit có thể là 0b00, 0b01hoặc 0b10. Hãy thử giải quyết vấn đề này trên 2 bit ..

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

Đây là những gì được yêu cầu: cột cuối cùng hiển thị số lượng các bit đã đặt trong mỗi cặp bit hai. Nếu số hai bit >= 2 (0b10)thì được andtạo ra 0b01, nếu số bit khác được tạo ra 0b00.

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

Tuyên bố này phải dễ hiểu. Sau thao tác đầu tiên, chúng ta có số lượng bit đã đặt trong mỗi hai bit, bây giờ chúng ta tính tổng số đó trong mỗi 4 bit.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Sau đó, chúng tôi tổng hợp kết quả trên, cho chúng tôi tổng số bit đặt trong 4 bit. Tuyên bố cuối cùng là khó nhất.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Hãy chia nhỏ nó hơn nữa ...

v + (v >> 4)

Nó tương tự như câu lệnh thứ hai; thay vào đó, chúng tôi đang đếm các bit đã đặt trong nhóm 4. Chúng tôi biết - vì các hoạt động trước đây của chúng tôi - rằng mỗi nibble đều có số lượng bit đã đặt trong đó. Hãy xem một ví dụ. Giả sử chúng ta có byte 0b01000010. Nó có nghĩa là cái thứ nhất có 4bits và cái thứ hai có 2bits. Bây giờ chúng ta thêm những thứ đó lại với nhau.

0b01000010 + 0b01000000

Nó cung cấp cho chúng tôi số lượng các bit đã đặt trong một byte, trong nibble đầu tiên 0b01100010và do đó chúng tôi che dấu bốn byte cuối cùng của tất cả các byte trong số (loại bỏ chúng).

0b01100010 & 0xF0 = 0b01100000

Bây giờ mỗi byte đều có số lượng bit đã đặt trong đó. Chúng ta cần thêm tất cả chúng lại với nhau. Bí quyết là nhân kết quả 0b10101010có một thuộc tính thú vị. Nếu số của chúng ta có bốn byte, A B C Dnó sẽ dẫn đến một số mới với các byte này A+B+C+D B+C+D C+D D. Một số 4 byte có thể có tối đa 32 bit được đặt, có thể được biểu diễn dưới dạng 0b00100000.

Tất cả những gì chúng ta cần bây giờ là byte đầu tiên có tổng của tất cả các bit đã đặt trong tất cả các byte và chúng ta lấy nó bằng cách >> 24. Thuật toán này được thiết kế cho các 32 bittừ nhưng có thể dễ dàng sửa đổi cho các 64 bittừ.

56
Noether 2008-09-21 09:14.

Nếu bạn tình cờ sử dụng Java, phương thức tích hợp Integer.bitCountsẽ thực hiện điều đó.

55
3 revs Mike F 2008-09-25 16:46.

Tôi cảm thấy nhàm chán, và tính toán một tỷ lần lặp lại ba cách tiếp cận. Trình biên dịch là gcc -O3. CPU là bất cứ thứ gì họ đưa vào Macbook Pro thế hệ thứ nhất.

Nhanh nhất là 3,7 giây sau:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

Vị trí thứ hai thuộc về cùng một mã nhưng tìm kiếm 4 byte thay vì 2 nửa từ. Điều đó mất khoảng 5,5 giây.

Vị trí thứ ba thuộc về cách tiếp cận 'bổ sung sang một bên', mất 8,6 giây.

Vị trí thứ tư thuộc về __builtin_popcount () của GCC, với 11 giây đáng xấu hổ.

Phương pháp đếm từng bit một ngày càng chậm hơn và tôi cảm thấy nhàm chán khi phải chờ đợi nó hoàn thành.

Vì vậy, nếu bạn quan tâm đến hiệu suất trên hết thì hãy sử dụng cách tiếp cận đầu tiên. Nếu bạn quan tâm, nhưng không đủ 64Kb RAM cho nó, hãy sử dụng cách tiếp cận thứ hai. Nếu không, hãy sử dụng phương pháp đọc từng bit một (nhưng chậm).

Thật khó để nghĩ ra một tình huống mà bạn muốn sử dụng phương pháp xoay vòng bit.

Chỉnh sửa: Kết quả tương tự tại đây .

31
abcdabcd987 2012-08-06 02:47.
unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

Hãy để tôi giải thích thuật toán này.

Thuật toán này dựa trên Thuật toán Chia và Chinh phục. Giả sử có một số nguyên 8bit 213 (11010101 trong hệ nhị phân), thuật toán hoạt động như thế này (mỗi lần hợp nhất hai khối hàng xóm):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+
29
user183351 2009-10-03 11:34.

Đây là một trong những câu hỏi giúp biết được kiến ​​trúc vi mô của bạn. Tôi vừa tính thời gian cho hai biến thể trong gcc 4.3.3 được biên dịch với -O3 bằng cách sử dụng nội tuyến C ++ để loại bỏ chi phí gọi hàm, một tỷ lần lặp, giữ tổng số đang chạy của tất cả các số để đảm bảo trình biên dịch không loại bỏ bất kỳ thứ gì quan trọng, sử dụng rdtsc để định thời ( chu kỳ đồng hồ chính xác).

inline int pop2 (không dấu x, không dấu y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    trả về (x + y) & 0x000000FF;
}

Hacker's Delight chưa được sửa đổi đã chiếm 12,2 gigac cycle. Phiên bản song song của tôi (đếm gấp đôi số bit) chạy trong 13.0 gigacycles. Tổng cộng 10,5 giây đã trôi qua cho cả hai cùng nhau trên Core Duo 2,4 GHz. 25 gigacycles = chỉ hơn 10 giây ở tần số đồng hồ này, vì vậy tôi tự tin rằng thời gian của mình là đúng.

Điều này liên quan đến các chuỗi phụ thuộc hướng dẫn, điều này rất tệ đối với thuật toán này. Tôi có thể tăng gần gấp đôi tốc độ một lần nữa bằng cách sử dụng một cặp thanh ghi 64-bit. Trên thực tế, nếu tôi khéo léo và thêm x + ya sớm hơn một chút, tôi có thể cạo bớt một số ca. Phiên bản 64-bit với một số chỉnh sửa nhỏ sẽ xuất hiện về số chẵn, nhưng đếm lại số bit nhiều gấp đôi.

Với các thanh ghi SIMD 128 bit, một hệ số khác là hai, và các tập lệnh SSE cũng thường có các đường tắt thông minh.

Không có lý do gì để mã đặc biệt minh bạch. Giao diện đơn giản, thuật toán có thể được tham chiếu trực tuyến ở nhiều nơi và có thể kiểm tra đơn vị toàn diện. Lập trình viên tình cờ gặp nó thậm chí có thể học được điều gì đó. Các hoạt động bit này diễn ra vô cùng tự nhiên ở cấp độ máy.

OK, tôi đã quyết định chọn phiên bản 64-bit đã được tinh chỉnh. Đối với một sizeof (dài không dấu) này == 8

inline int pop2 (unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    trả về x & 0xFF;
}

Điều đó có vẻ đúng (mặc dù tôi không thử nghiệm cẩn thận). Giờ đây, thời gian xuất hiện ở mức 10,70 gigacycles / 14,1 gigacycles. Con số sau đó tổng hợp 128 tỷ bit và tương ứng với 5,9 giây trôi qua trên máy này. Phiên bản không song song tăng tốc một chút vì tôi đang chạy ở chế độ 64-bit và nó thích các thanh ghi 64-bit tốt hơn một chút so với các thanh ghi 32-bit.

Hãy xem liệu có thêm một chút đường ống OOO nào ở đây không. Điều này có liên quan nhiều hơn một chút, vì vậy tôi thực sự đã thử nghiệm một chút. Riêng mỗi số hạng tính bằng 64, tất cả cộng lại thành 256.

inline int pop4 (unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  enum {m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF};

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    trả về x & 0x000001FF;
}

Tôi đã rất phấn khích trong giây lát, nhưng hóa ra gcc đang chơi thủ thuật nội tuyến với -O3 mặc dù tôi không sử dụng từ khóa nội tuyến trong một số bài kiểm tra. Khi tôi để gcc chơi thủ thuật, một tỷ lệnh gọi đến pop4 () mất 12,56 gigacycles, nhưng tôi xác định rằng đó là các đối số gấp dưới dạng biểu thức hằng. Một con số thực tế hơn dường như là 19,6gc để tăng tốc thêm 30%. Vòng lặp kiểm tra của tôi bây giờ trông giống như thế này, đảm bảo rằng mỗi đối số đủ khác nhau để ngăn gcc chơi thủ thuật.

   hitime b4 = rdtsc (); 
   for (dài không dấu i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
      sum + = pop4 (i, i ^ 1, ~ i, i | 1); 
   hitime e4 = rdtsc (); 

256 tỷ bit được tổng hợp trong 8,17 giây trôi qua. Hoạt động tới 1,02 giây cho 32 triệu bit như được chuẩn hóa trong tra cứu bảng 16 bit. Không thể so sánh trực tiếp, bởi vì băng ghế dự bị khác không cung cấp tốc độ đồng hồ, nhưng có vẻ như tôi đã tát mũi ra khỏi phiên bản bảng 64KB, đó là việc sử dụng bộ nhớ cache L1 một cách thảm hại ngay từ đầu.

Cập nhật: quyết định làm điều hiển nhiên và tạo pop6 () bằng cách thêm bốn dòng trùng lặp. Phát ra đến 22,8gc, 384 tỷ bit được tổng hợp trong 9,5 giây trôi qua. Vì vậy, có 20% khác Bây giờ ở 800ms cho 32 tỷ bit.

29
daniel 2008-09-21 09:10.

Tại sao không chia lặp lại cho 2?

đếm = 0
trong khi n> 0
  if (n% 2) == 1
    đếm + = 1
  n / = 2  

Tôi đồng ý rằng đây không phải là nhanh nhất, nhưng "tốt nhất" hơi mơ hồ. Tôi tranh luận mặc dù "tốt nhất" nên có một yếu tố rõ ràng

26
John Dimm 2013-12-20 20:55.

Bit của Hacker's Delight trở nên rõ ràng hơn rất nhiều khi bạn viết ra các mẫu bit.

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

Bước đầu tiên thêm các bit chẵn vào các bit lẻ, tạo ra tổng các bit trong mỗi hai. Các bước khác thêm các khối bậc cao vào các khối bậc thấp, tăng gấp đôi kích thước khối cho đến khi chúng ta có số cuối cùng chiếm toàn bộ số nguyên.

22
PhirePhly 2008-09-22 17:55.

Để có phương tiện hài lòng giữa bảng tra cứu 2 32 và lặp lại từng bit riêng lẻ:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

Từ http://ctips.pbwiki.com/CountBits

19
herohuyongtao 2014-01-15 02:53.

Điều này có thể được thực hiện trong O(k), ksố lượng bit được thiết lập ở đâu.

int NumberOfSetBits(int n)
{
    int count = 0;

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

    return count;
}
17
Peter 2012-10-20 02:31.

Đó không phải là giải pháp nhanh nhất hay tốt nhất, nhưng tôi đã tìm thấy câu hỏi tương tự theo cách của mình, và tôi bắt đầu suy nghĩ và suy nghĩ. cuối cùng tôi nhận ra rằng nó có thể được thực hiện như thế này nếu bạn nhận được vấn đề từ khía cạnh toán học và vẽ một biểu đồ, sau đó bạn thấy rằng đó là một hàm có một số phần tuần hoàn, và sau đó bạn nhận ra sự khác biệt giữa các giai đoạn ... vì vậy của bạn đây:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}
10
Michael Dorfman 2008-09-23 23:20.

Hàm bạn đang tìm kiếm thường được gọi là "tổng đi ngang" hoặc "đếm dân số" của một số nhị phân. Knuth thảo luận về nó trong Pre-Fascicle 1A, trang 11-12 (mặc dù có một tài liệu tham khảo ngắn gọn trong Tập 2, 4.6.3- (7).)

Các classicus locus là bài viết Peter Wegner của "Một kỹ thuật cho Ones đếm trong một máy tính nhị phân", từ truyền thông của ACM , Tập 3 (1960) Số 5, trang 322 . Ông đưa ra hai thuật toán khác nhau ở đó, một thuật toán được tối ưu hóa cho các số được mong đợi là "thưa thớt" (tức là có số lượng nhỏ) và một cho trường hợp ngược lại.

10
stacktay 2017-11-09 04:50.
  private int get_bits_set(int v)
    {
      int c; // c accumulates the total bits set in v
        for (c = 0; v>0; c++)
        {
            v &= v - 1; // clear the least significant bit set
        }
        return c;
    }
9
Baban 2010-05-07 18:51.

Vài câu hỏi mở: -

  1. Nếu số âm thì?
  2. Nếu số là 1024, thì phương pháp "chia lần lượt cho 2" sẽ lặp lại 10 lần.

chúng ta có thể sửa đổi bí danh để hỗ trợ số âm như sau: -

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

bây giờ để khắc phục vấn đề thứ hai, chúng ta có thể viết thuật ngữ như: -

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

để tham khảo đầy đủ, hãy xem:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

9
Erorr 2016-06-01 16:16.

Tôi nghĩ rằng phương pháp của Brian Kernighan cũng sẽ hữu ích ... Nó trải qua nhiều lần lặp lại vì có các bit được thiết lập. Vì vậy, nếu chúng ta có một từ 32-bit chỉ có bộ bit cao, thì nó sẽ chỉ đi qua vòng lặp một lần.

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

Được xuất bản vào năm 1988, Ngôn ngữ lập trình C lần thứ 2 Ed. (của Brian W. Kernighan và Dennis M. Ritchie) đề cập đến điều này trong bài tập 2-9. Vào ngày 19 tháng 4 năm 2006, Don Knuth đã chỉ ra cho tôi rằng phương pháp này "được Peter Wegner công bố lần đầu tiên trong CACM 3 (1960), 322. (Cũng được phát hiện độc lập bởi Derrick Lehmer và được xuất bản vào năm 1964 trong một cuốn sách do Beckenbach biên tập.)"

8
Manish Mulani 2012-05-05 21:12.

Tôi sử dụng mã dưới đây trực quan hơn.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Logic: n & (n-1) đặt lại bit cuối cùng của n.

Tái bút: Tôi biết đây không phải là giải pháp O (1), mặc dù là một giải pháp thú vị.

7
Horcrux7 2008-09-21 09:31.

Ý bạn là gì với "Thuật toán tốt nhất"? Mã được rút gọn hay mã được gắn chặt? Mã của bạn trông rất thanh lịch và nó có thời gian thực thi không đổi. Mã cũng rất ngắn.

Nhưng nếu tốc độ là yếu tố chính chứ không phải kích thước mã thì tôi nghĩ phần sau có thể nhanh hơn:

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

Tôi nghĩ rằng điều này sẽ không nhanh hơn đối với giá trị 64 bit nhưng giá trị 32 bit có thể nhanh hơn.

7
systemBuilder 2010-06-12 11:40.

Tôi đã viết macro số lượng bit nhanh cho các máy RISC vào khoảng năm 1990. Nó không sử dụng số học nâng cao (nhân, chia,%), tìm nạp bộ nhớ (quá chậm), các nhánh (quá chậm), nhưng nó giả sử CPU có Bộ dịch chuyển thùng 32-bit (nói cách khác, >> 1 và >> 32 có cùng số lượng chu kỳ.) Nó giả định rằng các hằng số nhỏ (chẳng hạn như 6, 12, 24) không tốn gì để tải vào thanh ghi hoặc được lưu trữ trong thời gian tạm thời và được sử dụng lại nhiều lần.

Với những giả định này, nó đếm 32 bit trong khoảng 16 chu kỳ / lệnh trên hầu hết các máy RISC. Lưu ý rằng 15 lệnh / chu kỳ gần với giới hạn dưới về số chu kỳ hoặc lệnh, vì có vẻ như cần ít nhất 3 lệnh (mặt nạ, shift, toán tử) để cắt giảm một nửa số lượng phụ kiện, vì vậy log_2 (32) = 5, 5 x 3 = 15 hướng dẫn là một giới hạn gần như thấp hơn.

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

Đây là bí mật cho bước đầu tiên và phức tạp nhất:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

vì vậy nếu tôi lấy cột đầu tiên (A) ở trên, dịch chuyển nó sang phải 1 bit, và trừ nó khỏi AB, tôi nhận được đầu ra (CD). Phần mở rộng đến 3 bit cũng tương tự; bạn có thể kiểm tra nó bằng bảng boolean 8 hàng như của tôi ở trên nếu bạn muốn.

  • Don Gillies
7
pentaphobe 2012-04-04 18:25.

nếu bạn đang sử dụng C ++, một tùy chọn khác là sử dụng lập trình ẩn mẫu:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

cách sử dụng sẽ là:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

tất nhiên bạn có thể mở rộng thêm mẫu này để sử dụng các loại khác nhau (thậm chí cả kích thước bit tự động phát hiện) nhưng tôi đã giữ nó đơn giản cho rõ ràng.

chỉnh sửa: quên đề cập điều này là tốt vì nó sẽ hoạt động trong bất kỳ trình biên dịch C ++ nào và về cơ bản nó chỉ giải nén vòng lặp của bạn cho bạn nếu một giá trị hằng số được sử dụng cho số lượng bit (nói cách khác, tôi khá chắc rằng đó là phương pháp chung nhanh nhất bạn sẽ tìm thấy)

6
Ross 2008-09-23 15:29.

Tôi đặc biệt thích ví dụ này từ tệp tài sản:

#define BITCOUNT (x) (((BX_ (x) + (BX_ (x) >> 4)) & 0x0F0F0F0F)% 255)
#define BX_ (x) ((x) - (((x) >> 1) & 0x77777777)
                             - (((x) >> 2) & 0x33333333)
                             - (((x) >> 3) & 0x11111111))

Tôi thích nó nhất vì nó rất đẹp!

6
Rahul 2010-12-11 10:40.

Java JDK1.5

Số nguyên.bitCount (n);

trong đó n là số có 1 được đếm.

cũng kiểm tra,

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }
6
ErmIg 2016-02-16 04:33.

Tôi đã tìm thấy một triển khai đếm bit trong một mảng bằng cách sử dụng lệnh SIMD (SSSE3 và AVX2). Nó có hiệu suất tốt hơn 2-2,5 lần so với nếu nó sẽ sử dụng hàm nội tại __popcnt64.

Phiên bản SSSE3:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

Phiên bản AVX2:

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}
6
diugalde 2016-11-04 11:02.

Tôi luôn sử dụng điều này trong Lập trình cạnh tranh và nó rất dễ viết và hiệu quả:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}
6
Varun Gusain 2017-08-24 07:31.

những gì bạn có thể làm là

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

logic đằng sau điều này là các bit của n-1 được đảo ngược từ bit đặt ngoài cùng bên phải của n. nếu n = 6 tức là 110 thì 5 là 101 các bit được đảo ngược từ bit đặt ngoài cùng bên phải của n. vì vậy nếu chúng ta và hai người này, chúng ta sẽ tạo bit 0 ngoài cùng bên phải trong mỗi lần lặp và luôn chuyển đến bit đặt ngoài cùng bên phải tiếp theo. Do đó, đếm bit đã đặt. Độ phức tạp thời gian tồi tệ nhất sẽ là O (logn) khi mọi bit được đặt.

C ++ 20 std::popcount

Đề xuất sau đã được hợp nhất http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.htmlvà nên thêm nó vào <bit>tiêu đề.

Tôi mong đợi việc sử dụng sẽ như sau:

#include <bit>
#include <iostream>

int main() {
    std::cout << std::popcount(0x55) << std::endl;
}

Tôi sẽ thử khi hỗ trợ đến GCC, GCC 9.1.0 mà g++-9 -std=c++2avẫn không hỗ trợ.

Đề xuất nói:

Tiêu đề: <bit>

namespace std {

  // 25.5.6, counting
  template<class T>
    constexpr int popcount(T x) noexcept;

và:

template<class T>
  constexpr int popcount(T x) noexcept;

Ràng buộc: T là kiểu số nguyên không dấu (3.9.1 [basic.fundaries]).

Trả về: Số bit 1 trong giá trị của x.

std::rotlstd::rotrcũng được thêm vào để thực hiện các phép quay bit tròn: Các phương pháp hay nhất cho các hoạt động dịch chuyển (xoay) vòng tròn trong C ++

5
Mostafa 2011-04-13 21:50.

Có nhiều thuật toán để đếm các bit đã đặt; nhưng tôi nghĩ cái tốt nhất là cái nhanh hơn! Bạn có thể xem chi tiết trên trang này:

Bit Twiddling Hacks

Tôi đề nghị cái này:

Đếm số bit được đặt trong các từ 14, 24 hoặc 32 bit bằng cách sử dụng lệnh 64 bit

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Phương pháp này yêu cầu CPU 64-bit với phân chia mô-đun nhanh để có hiệu quả. Tùy chọn đầu tiên chỉ mất 3 thao tác; phương án thứ hai lấy 10; và tùy chọn thứ ba mất 15.

5
dadhi 2014-01-31 01:32.

Giải pháp C # nhanh bằng cách sử dụng bảng đếm bit Byte được tính toán trước với sự phân nhánh trên kích thước đầu vào.

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Desiree Rogers, trái, và Cheryl Mayberry McKissack Chuyển sang, Fenty Beauty và Pat McGrath, có một đế chế làm đẹp mới do phụ nữ làm chủ đang trỗi dậy. Sau thương vụ mua lại mỹ phẩm Black Opal vào tháng 9, đội ngũ quyền lực của Giám đốc điều hành công ty Desiree Rogers và Chủ tịch Cheryl Mayberry McKissack đã thông báo mua lại thương hiệu làm đẹp tiên phong Fashion Fair từ người sáng lập Johnson Publishing Company (JPC).

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Đối với những người có quá nhiều thời gian, tiệc tiết lộ giới tính là một cách thú vị để không cần áp đặt những định kiến ​​hạn chế lên thai nhi trước một đối tượng bạn bè giả vờ quan tâm một cách lịch sự. Tuy nhiên, việc chỉ dựa vào những chiếc bánh nướng có màu nhân tạo để biểu thị một tiếng hoo-ha hoặc một đứa trẻ đi tè đã trở nên xa xỉ trong các bậc cha mẹ trên Instagram.

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Hôm thứ Tư, cựu Bộ trưởng An ninh Nội địa Kirstjen Nielsen vì một lý do nào đó đã được đưa ra một diễn đàn để phát biểu tại Hội nghị thượng đỉnh Những người phụ nữ quyền lực nhất của Fortune. Và có thể đoán trước được, người phụ nữ giám sát các nỗ lực (đang diễn ra) của chính quyền Trump nhằm chia cắt các gia đình ở biên giới đã sử dụng thời gian của mình như một cơ hội để tự bảo vệ mình và tự nhận mình là người — và hãy hít thở sâu ở đây — “đã nói sự thật với quyền lực.

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Vì thế hệ mới nhất của chiếc xe điều chỉnh được yêu thích trên thế giới hiện đã có mặt tại đây, nên chỉ có điều kiện là Toyota Racing Development sẽ đưa phiên bản Supra thế hệ thứ năm sửa đổi của riêng mình đến SEMA vào tháng tới. Toyota đã cho chúng tôi một gợi ý về những gì sẽ xảy ra trong tuần này: một chiếc Concept GR Supra 3000GT hiện đại.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language