[algorithm] Как подсчитать количество заданных битов в 32-битовом целое?



Answers

Также рассмотрите встроенные функции ваших компиляторов.

Например, в компиляторе GNU вы можете просто использовать:

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

В худшем случае компилятор будет генерировать вызов функции. В лучшем случае компилятор будет выдавать инструкцию cpu для выполнения той же самой работы быстрее.

Собственные средства GCC работают даже на нескольких платформах. Popcount станет основной темой в архитектуре x86, поэтому имеет смысл начать использовать внутреннее значение. Другие архитектуры имеют много лет.

На x86 вы можете сказать компилятору, что он может взять на себя поддержку инструкции popcnt с помощью -mpopcnt или -msse4.2 чтобы также включить векторные инструкции, которые были добавлены в том же поколении. См. Параметры GCC x86 . -march=nehalem (или -march= любой процессор, который вы хотите, чтобы ваш код принимал и настраивал) мог бы быть хорошим выбором. Запуск полученного двоичного файла на более старый процессор приведет к ошибке с неправильной инструкцией.

Чтобы оптимизировать бинарные файлы для машины, на которой вы их построили, используйте -march=native (с gcc, clang или ICC).

MSVC обеспечивает встроенную команду x86 popcnt , но в отличие от gcc она действительно является неотъемлемой popcnt аппаратной инструкции и требует аппаратной поддержки.

Использование std::bitset<>::count() вместо встроенного

Теоретически любой компилятор, который знает, как эффективно использовать popcount для целевого ЦП, должен раскрывать эту функциональность через ISO C ++ std::bitset<> . На практике вам может быть лучше с бит-взломом AND / shift / ADD в некоторых случаях для некоторых целевых CPU.

Для целевых архитектур, где аппаратный popcount является дополнительным расширением (например, x86), не все компиляторы имеют std::bitset который использует его, когда он доступен. Например, MSVC не имеет возможности включить поддержку popcnt во время компиляции и всегда использует поиск в таблице , даже с /Ox /arch:AVX (что подразумевает SSE4.2, хотя технически для popcnt есть отдельный бит popcnt ).

Но по крайней мере вы получаете что-то портативное, которое работает повсеместно, и с gcc / clang с правильными целевыми параметрами вы получаете аппаратный popcount для архитектур, которые его поддерживают.

#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();
}

См. Asm из gcc, clang, icc и MSVC в проводнике компилятора Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt испускает это:

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++11 испускает (для версии int arg):

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

Этот источник не является специфичным для x86 или GNU-специфичным, но только хорошо компилируется для x86 с gcc / clang / icc.

Также обратите внимание, что резервное копирование gcc для архитектур без всплывающей подсказки с одной инструкцией представляет собой поиск по байтам по времени. Например, это не удивительно для ARM .

Question

8 бит, представляющих число 7, выглядят следующим образом:

00000111

Три бита установлены.

Что такое алгоритмы для определения количества битов в 32-битном целом?




I wrote a fast bitcount macro for RISC machines in about 1990. It does not use advanced arithmetic (multiplication, division, %), memory fetches (way too slow), branches (way too slow), but it does assume the CPU has a 32-bit barrel shifter (in other words, >> 1 and >> 32 take the same amount of cycles.) It assumes that small constants (such as 6, 12, 24) cost nothing to load into the registers, or are stored in temporaries and reused over and over again.

With these assumptions, it counts 32 bits in about 16 cycles/instructions on most RISC machines. Note that 15 instructions/cycles is close to a lower bound on the number of cycles or instructions, because it seems to take at least 3 instructions (mask, shift, operator) to cut the number of addends in half, so log_2(32) = 5, 5 x 3 = 15 instructions is a quasi-lowerbound.

#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;

Here is a secret to the first and most complex step:

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

so if I take the 1st column (A) above, shift it right 1 bit, and subtract it from AB, I get the output (CD). The extension to 3 bits is similar; you can check it with an 8-row boolean table like mine above if you wish.

  • Don Gillies



I found an implementation of bit counting in an array with using of SIMD instruction (SSSE3 and AVX2). It has in 2-2.5 times better performance than if it will use __popcnt64 intrinsic function.

SSSE3 version:

#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];
}

AVX2 version:

#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];
}



Мне стало скучно и приурочено к миллиарду итераций трех подходов. Компилятор - gcc-O3. CPU - это то, что они поставили в первом поколении Macbook Pro.

Самый быстрый из них: 3,7 секунды:

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] );
}

Второе место относится к одному и тому же коду, но поиск 4 байта вместо 2-х половин. Это заняло около 5,5 секунд.

Третье место относится к подходу «бокового сложения», который занял 8,6 секунды.

Четвертое место занимает GCC __builtin_popcount (), постыдное 11 секунд.

Подсчет одного-двух-на-время подхода был waaaay медленнее, и мне стало скучно ждать его завершения.

Поэтому, если вы заботитесь о производительности выше всех остальных, используйте первый подход. Если вам все равно, но недостаточно, чтобы потратить на нее 64 КБ ОЗУ, используйте второй подход. В противном случае используйте читаемый (но медленный) подход с одним битом по времени.

Трудно представить себе ситуацию, когда вы захотите использовать подход, основанный на битах.

Изменить: похожие результаты here .




Here is a portable module ( ANSI-C ) which can benchmark each of your algorithms on any architecture.

Your CPU has 9 bit bytes? No problem :-) At the moment it implements 2 algorithms, the K&R algorithm and a byte wise lookup table. The lookup table is on average 3 times faster than the K&R algorithm. If someone can figure a way to make the "Hacker's Delight" algorithm portable feel free to add it in.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

,

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif



Взлом Хакер-Хедлайнера становится намного яснее, когда вы выписываете битовые паттерны.

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;
}

Первый шаг добавляет четные биты к нечетным битам, создавая сумму бит в каждом двоичном разряде. Другие шаги добавляют куски высокого порядка к кускам младшего порядка, удваивая размер куска до тех пор, пока мы не получим окончательный счет, занимающий весь int.




  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;
    }



Почему не итеративно делить на 2?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

Я согласен, что это не самый быстрый, но «лучший» несколько неоднозначен. Я бы сказал, что «лучший» должен иметь элемент ясности




I think the Brian Kernighan's method will be useful too... It goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

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; 
}

Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to me that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"




Few open questions:-

  1. If the number is negative then?
  2. If the number is 1024 , then the "iteratively divide by 2" method will iterate 10 times.

we can modify the algo to support the negative number as follows:-

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

now to overcome the second problem we can write the algo like:-

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

for complete reference see :

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




Это один из тех вопросов, где он помогает узнать вашу микро-архитектуру. Я просто приурочил два варианта под gcc 4.3.3, скомпилированный с -O3, используя C ++ inline, чтобы устранить накладные расходы на вызовы функций, один миллиард итераций, сохраняя текущую сумму всех счетчиков, чтобы гарантировать, что компилятор не удаляет ничего важного, используя rdtsc для синхронизации ( тактовый цикл).

inline int pop2(unsigned x, unsigned 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);
    return (x+y) & 0x000000FF;
}

Unmodified Hacker's Delight занял 12,2 гигацикла. Моя параллельная версия (считая в два раза больше бит) работает в 13.0 gigacycles. Всего 10,5 с обоих вместе взятых на Core Duo 2,4 ГГц. 25 gigacycles = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои тайминги правильные.

Это связано с цепочками зависимостей команд, которые очень плохо для этого алгоритма. Я мог бы удвоить скорость снова, используя пару 64-битных регистров. На самом деле, если бы я был умным и добавил х + я немного раньше, я мог бы сбрить некоторые смены. 64-битная версия с некоторыми небольшими настройками выйдет примерно ровно, но пересчитайте в два раза больше бит.

С 128-битными SIMD-регистрами, еще одним фактором из двух, и наборы инструкций SSE часто также имеют умные сокращения.

Нет никакой причины, чтобы код был особенно прозрачным. Интерфейс прост, алгоритм можно ссылаться в режиме онлайн во многих местах, и он подлежит всеобъемлющему модульному тесту. Программист, который натыкается на него, может даже что-то узнать. Эти битовые операции чрезвычайно естественны на уровне машины.

Хорошо, я решил поставить исправленную 64-битную версию. Для этого один sizeof (unsigned long) == 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); 
    return x & 0xFF;
}

Это выглядит правильно (я не тщательно тестирую). Теперь тайминга выходят на 10,70 гигацикла / 14,1 гигацикла. Это более позднее число суммировало 128 миллиардов бит и соответствует 5.9s, прошедшим на этой машине. Непараллельная версия ускоряет крошечный бит, потому что я работаю в 64-битном режиме, и он любит 64-битные регистры немного лучше, чем 32-разрядные регистры.

Посмотрим, есть ли здесь еще несколько конвейеров ООО. Это было немного более активно, поэтому я фактически немного протестировал. Каждый член сам по себе суммируется до 64, а вся сумма - 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);
    return x & 0x000001FF;
}

Я был взволнован на мгновение, но оказалось, что gcc играет встроенные трюки с -O3, хотя я не использую ключевое слово inline в некоторых тестах. Когда я позволяю gcc играть трюки, миллиард звонков в pop4 () принимает 12.56 гигациклов, но я решил, что это аргументы сгибания как постоянные выражения. Более реалистичное число, по-видимому, составляет 19.6gc для еще 30% ускорения. Мой тестовый цикл теперь выглядит так, чтобы каждый аргумент был достаточно разным, чтобы остановить gcc от трюков.

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

256 миллиардов бит, суммированных в 8.17s, истекли. Работает до 1.02s для 32 миллионов бит, сравнивая результаты поиска в 16 бит. Невозможно сравнивать напрямую, потому что другая скамейка не дает тактовой частоты, но выглядит так, как будто я ударил сопли из таблицы на 64 КБ, что является трагическим использованием кеша L1 в первую очередь.

Обновление: решил сделать очевидное и создать pop6 (), добавив еще четыре дублированные строки. Вышло до 22,8 гц, и 384 млрд. Бит суммировано в 9,5 с. Так что есть еще 20%. Теперь на 800 мс за 32 миллиарда бит.




Fast C# solution using pre-calculated table of Byte bit counts with branching on input size.

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
    };
}



This can be done in O(k) , where k is the number of bits set.

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

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

    return count;
}



I'm particularly fond of this example from the fortune file:

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

I like it best because it's so pretty!




Из восторга Хакер, с. 66, Рисунок 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;
}

Выполняется в ~ 20-их инструкциях (зависит от дуги), без ветвления.

Удовольствие Хакер восхитительно! Настоятельно рекомендуется.




Related