यहां कुछ कोड हैं जिनका उपयोग मैंने पुराने प्रोजेक्ट (there is a research paper about it) में किया था। फंक्शन popcnt8
नीचे प्रत्येक बाइट में सेट बिट्स की संख्या की गणना करता है।
SSE2-केवल संस्करण (Hacker's Delight book में एल्गोरिथ्म 3 के आधार पर):
static const __m128i popcount_mask1 = _mm_set1_epi8(0x77);
static const __m128i popcount_mask2 = _mm_set1_epi8(0x0F);
static inline __m128i popcnt8(__m128i x) {
__m128i n;
// Count bits in each 4-bit field.
n = _mm_srli_epi64(x, 1);
n = _mm_and_si128(popcount_mask1, n);
x = _mm_sub_epi8(x, n);
n = _mm_srli_epi64(n, 1);
n = _mm_and_si128(popcount_mask1, n);
x = _mm_sub_epi8(x, n);
n = _mm_srli_epi64(n, 1);
n = _mm_and_si128(popcount_mask1, n);
x = _mm_sub_epi8(x, n);
x = _mm_add_epi8(x, _mm_srli_epi16(x, 4));
x = _mm_and_si128(popcount_mask2, x);
return x;
}
SSSE3 संस्करण (Wojciech Mula के कारण):
static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static inline __m128i popcnt8(__m128i n) {
const __m128i pcnt0 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(n, popcount_mask));
const __m128i pcnt1 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(_mm_srli_epi16(n, 4), popcount_mask));
return _mm_add_epi8(pcnt0, pcnt1);
}
XOP संस्करण (SSSE3 के बराबर है, लेकिन XOP निर्देश का उपयोग करता है जो एएमडी बुलडोजर पर तेज़ हैं)
static const __m128i popcount_mask = _mm_set1_epi8(0x0F);
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
static const __m128i popcount_shift = _mm_set1_epi8(-4);
static inline __m128i popcount8(__m128i n) {
const __m128i pcnt0 = _mm_perm_epi8(popcount_table, popcount_table, _mm_and_si128(n, popcount_mask));
const __m128i pcnt1 = _mm_perm_epi8(popcount_table, popcount_table, _mm_shl_epi8(n, popcount_shift));
return _mm_add_epi8(pcnt0, pcnt1);
}
फ़ंक्शन आयन popcnt64
नीचे SSE के निम्न और उच्च 64-बिट हिस्सों में बिट्स की संख्या की गणना रजिस्टर:
SSE2 संस्करण:
static inline __m128i popcnt64(__m128i n) {
const __m128i cnt8 = popcnt8(n);
return _mm_sad_epu8(cnt8, _mm_setzero_si128());
}
XOP संस्करण:
static inline __m128i popcnt64(__m128i n) {
const __m128i cnt8 = popcnt8(n);
return _mm_haddq_epi8(cnt8);
}
अंत में, समारोह popcnt128
पूरे 128-बिट रजिस्टर में बिट्स की संख्या की गणना करें:
static inline int popcnt128(__m128i n) {
const __m128i cnt64 = popcnt64(n);
const __m128i cnt64_hi = _mm_unpackhi_epi64(cnt64, cnt64);
const __m128i cnt128 = _mm_add_epi32(cnt64, cnt64_hi);
return _mm_cvtsi128_si32(cnt128);
}
हालांकि, popcnt128
लागू करने के लिए एक अधिक कुशल तरीका (जो इसे समर्थन प्रोसेसर पर) हार्डवेयर POPCNT अनुदेश का उपयोग करने के लिए है:
static inline int popcnt128(__m128i n) {
const __m128i n_hi = _mm_unpackhi_epi64(n, n);
#ifdef _MSC_VER
return __popcnt64(_mm_cvtsi128_si64(n)) + __popcnt64(_mm_cvtsi128_si64(n_hi));
#else
return __popcntq(_mm_cvtsi128_si64(n)) + __popcntq(_mm_cvtsi128_si64(n_hi));
#endif
}
हाल CPU के लिए अन्य आंतरिक कार्यों के साथ-साथ कुछ अतिरिक्त फ़ंक्शन के समान नामकरण के साथ एक 'POPCNT' (जनसंख्या गिनती) है अनुदेश; जीसीसी ने इसे ''__builtin_popcount'] (http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) के माध्यम से अंतर्निहित किया है। –
इसके लिए http://graphics.stanford.edu/~seander/bithacks.html देखें और बहुत कुछ। –
एमएस में पॉपकैंट फ़ंक्शन भी हैं ... http://stackoverflow.com/questions/11114017/whats-the-difference-between-popcnt-and-mm-popcnt-u32 देखें ... ध्यान दें कि ये आवश्यक रूप से तेज़ नहीं हैं बिथैक; और अगर सरणी में बिट्स गिनती है, तो कुछ बिथैक फ़ंक्शंस कुछ हद तक तेज हैं। –