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





выражения хабр (26)


Вот портативный модуль (ANSI-C), который может сравнивать каждый из ваших алгоритмов с любой архитектурой.

Ваш процессор имеет 9 бит байтов? Нет проблем :-) На данный момент он реализует 2 алгоритма, алгоритм K & R и байтную таблицу поиска. Таблица поиска в среднем в 3 раза быстрее, чем алгоритм K & R. Если кто-то может понять способ сделать алгоритм «Хакерского наслаждения» портативным, не стесняйтесь его добавлять.

#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

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

00000111

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

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




Java JDK1.5

Integer.bitCount (п);

где n - число, чьи 1 должны быть подсчитаны.

проверьте также,

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



На мой взгляд, «лучшее» решение - это то, которое можно прочитать другим программистом (или оригинальным программистом два года спустя) без обильных комментариев. Вам может понадобиться самое быстрое или умное решение, которое некоторые уже предоставили, но в любое время я предпочитаю читаемость.

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

Если вам нужна больше скорости (и если вы хорошо документируете ее, чтобы помочь своим преемникам), вы можете использовать поиск в таблице:

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

Хотя они зависят от конкретных типов данных, поэтому они не являются переносимыми. Но, поскольку многие оптимизации производительности в любом случае не переносятся, это может не быть проблемой. Если вы хотите переносимости, я придерживаюсь читаемого решения.




Если вы используете Java, встроенный метод Integer.bitCount сделает это.




Я думаю, что самый быстрый способ - без использования справочных таблиц и popcount - заключается в следующем. Он подсчитывает установленные бит всего за 12 операций.

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

Он работает, потому что вы можете подсчитать общее количество заданных бит, разделив его на две половины, подсчитав количество заданных бит в обеих половинах и затем добавив их. Также знайте, как парадигма Divide and Conquer . Давайте подробно рассмотрим.

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

Количество бит в двух битах может быть 0b00 , 0b01 или 0b10 . Давайте попробуем это разобрать на 2 бита.

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

Это то, что требовалось: последний столбец показывает количество установленных битов в каждой битовой паре. Если два битовых номера >= 2 (0b10) то and производит 0b01 , иначе он производит 0b00 .

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

Это утверждение должно быть легко понятным. После первой операции у нас есть счет бит в каждом бите, теперь мы суммируем этот счет каждые 4 бита.

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

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

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

Давайте раскроем его дальше ...

v + (v >> 4)

Это похоже на второе утверждение; мы вместо этого подсчитываем множество бит в группах по 4. Мы знаем - из-за наших предыдущих операций - что каждый кусочек имеет в нем количество установленных бит. Давайте посмотрим пример. Предположим, что у нас есть байт 0b01000010 . Это означает, что первый полубайт имеет свои 4 бита, а второй - 2 бита. Теперь мы добавляем эти кусочки вместе.

0b01000010 + 0b01000000

Он дает нам количество бит в байте в первом 0b01100010 и поэтому мы маскируем последние четыре байта всех байтов в числе (отбрасывая их).

0b01100010 & 0xF0 = 0b01100000

Теперь каждый байт имеет в нем количество установленных бит. Мы должны добавить их вместе. Трюк состоит в том, чтобы умножить результат на 0b10101010 который имеет интересное свойство. Если наш номер имеет четыре байта, ABCD , это приведет к новому числу с этими байтами A+B+C+D B+C+D C+DD . Число в 4 байта может иметь максимум 32 бита, который может быть представлен как 0b00100000 .

Все, что нам нужно сейчас, это первый байт, который имеет сумму всех заданных битов во всех байтах, и мы получаем его на >> 24 . Этот алгоритм был разработан для 32 bit слов, но может быть легко модифицирован для 64 bit слов.




Я всегда использую это в Конкурентном программировании, и его легко написать и эффективно:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}



Я нашел реализацию подсчета бит в массиве с использованием команды SIMD (SSSE3 и AVX2). Он имеет производительность в 2-2,5 раза лучше, чем если бы он использовал встроенную функцию __popcnt64.

Версия 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];
}

Версия 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];
}



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

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.




Быстрое решение C # с использованием предварительно вычисленной таблицы байт-бит с разветвлением по размеру ввода.

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



Мне стало скучно и приурочено к миллиарду итераций трех подходов. Компилятор - 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 .




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

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



Что вы подразумеваете под «Лучшим алгоритмом»? Укороченный код или голодный код? Ваш код выглядит очень элегантно и имеет постоянное время выполнения. Код также очень короткий.

Но если скорость является основным фактором, а не размером кода, я думаю, что последующие действия могут быть быстрее:

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

Я думаю, что это будет не быстрее для 64-битного значения, но 32-битное значение может быть быстрее.




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

Например, в компиляторе 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 .




Для счастливой среды между таблицей 3232 и повторением каждого бита отдельно:

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

С http://ctips.pbwiki.com/CountBits




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

Позвольте мне объяснить этот алгоритм.

Этот алгоритм основан на алгоритме Divide и Conquer. Предположим, что существует 8-битное целое число 213 (11010101 в двоичном виде), алгоритм работает так (каждый раз слияние двух соседних блоков):

+-------------------------------+
| 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)
+-------------------------------+



Из восторга Хакер, с. 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-их инструкциях (зависит от дуги), без ветвления.

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




Существует множество алгоритмов для подсчета установленных битов; но я думаю, что лучший из них самый быстрый! Вы можете увидеть подробную информацию на этой странице:

Бит Twiddling Hacks

Я предлагаю следующее:

Счетные биты, установленные в 14, 24 или 32-битных словах с использованием 64-битных инструкций

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;

Этот метод требует, чтобы 64-разрядный процессор с быстрым модулем деления был эффективным. Первый вариант принимает только 3 операции; второй вариант занимает 10; а третий вариант - 15.




Я особенно люблю этот пример из файла судьбы:

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

Мне это нравится, потому что это так красиво!




если вы используете C ++, другой вариант - использовать метапрограммирование шаблона:

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

использование будет:

// 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 )

вы могли бы, конечно, еще больше расширить этот шаблон, чтобы использовать разные типы (даже для автоматического определения размера бит), но я сохранил его просто для ясности.

edit: забыл упомянуть, что это хорошо, потому что он должен работать в любом компиляторе C ++, и он в основном просто разворачивает ваш цикл для вас, если для подсчета бит используется постоянное значение (другими словами, я уверен, что это самый быстрый общий метод ты найдешь)




Я написал быстрый макрос битконов для машин RISC примерно в 1990 году. Он не использует расширенную арифметику (умножение, деление,%), выборки памяти (слишком медленные), ветви (слишком медленные), но он предполагает, что у процессора есть 32-битный сдвиг ствола (другими словами, >> 1 и >> 32 занимают одинаковое количество циклов.) Он предполагает, что небольшие константы (такие как 6, 12, 24) ничего не стоят загружать в регистры или сохраняются во временных и повторное использование снова и снова.

С этими предположениями он рассчитан на 32 бита примерно на 16 циклов / инструкций на большинстве машин RISC. Обратите внимание, что 15 инструкций / циклов близки к нижней границе числа циклов или инструкций, потому что для сокращения количества слагаемых пополам требуется как минимум 3 команды (маска, сдвиг, оператор), поэтому log_2 (32) = 5, 5 x 3 = 15 инструкций - это квази-нижняя граница.

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

Вот секрет первого и самого сложного шага:

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

поэтому, если взять первый столбец (A) выше, сдвинуть его вправо 1 бит и вычесть его из AB, я получаю вывод (CD). Расширение до 3 бит аналогично; вы можете проверить это с помощью 8-строчной логической таблицы, как показано выше, если хотите.

  • Don Gillies



32-бит или нет? Я только что пришел с этим методом на Java после прочтения « взлома интервью по кодированию » 4-го издания с упражнениями 5.5 (глава 5: Бит Манипуляция). Если младший значащий бит равен 1 приращению count, тогда сдвиньте вправо целое число.

public static int bitCount( int n){
    int count = 0;
    for (int i=n; i!=0; i = i >> 1){
        count += i & 1;
    }
    return count;
}

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




Это можно сделать в O(k), где kуказано количество бит.

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

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

    return count;
}



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

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

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




Это известно как « Хэмминг-вес », «popcount» или «боковое добавление».

«Лучший» алгоритм действительно зависит от того, на каком процессоре вы находитесь и на каком шаблоне использования.

Некоторые процессоры имеют одну встроенную инструкцию, а другие имеют параллельные инструкции, которые действуют на битовые векторы. Параллельные инструкции (например, x86's popcnt , на процессорах, где он поддерживается), почти наверняка будут самыми быстрыми. Некоторые другие архитектуры могут иметь медленную инструкцию, реализованную с микрокодированным циклом, который проверяет бит за цикл ( ссылка ).

Метод заполнения таблицы с заполненной таблицей может быть очень быстрым, если ваш процессор имеет большой кеш и / или вы выполняете большую часть этих инструкций в узком цикле. Однако он может пострадать из-за расхода «промаха в кеше», когда ЦП должен извлечь часть таблицы из основной памяти.

Если вы знаете, что ваши байты будут в основном 0 или более 1, тогда есть очень эффективные алгоритмы для этих сценариев.

Я считаю, что очень хорошим алгоритмом общего назначения является следующий, известный как «параллельный» или «алгоритм SWAR с переменной точностью». Я выразил это на псевдо-языке C-типа, вам может потребоваться настроить его для работы на определенном языке (например, используя uint32_t для C ++ и >>> в Java):

int numberOfSetBits(int i)
{
     // Java: 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;
}

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

Этот алгоритм с побайтовым SWAR может распараллеливаться в нескольких векторных элементах одновременно, а не в одном целочисленном регистре, для ускорения работы с CPU с SIMD, но без использования команды popcount. (например, код x86-64, который должен запускаться на любом процессоре, а не только в Nehalem или позже).

Однако наилучшим способом использования векторных инструкций для popcount обычно является использование переменной-shuffle для выполнения поиска по таблице для 4 бит в момент каждого байта параллельно. (4-битный индекс содержит 16 записей, хранящихся в векторном регистре).

На процессорах Intel аппаратная 64-битная команда popcnt может превзойти битовую параллельную реализацию SSSE3 PSHUFB примерно в 2 раза, но только если ваш компилятор правильно ее использует . В противном случае SSE может выйти значительно вперед. Более новые версии компилятора знают о проблеме ложной зависимости popcnt на Intel .

Рекомендации:

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)




Я использую приведенный ниже код, который более интуитивно понятен.

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

Логика: n & (n-1) сбрасывает последний бит набора n.

PS: Я знаю, что это не O (1) решение, хотя и интересное решение.




(Я никогда раньше этого не видел. Этот трюк замечательный!)

Я немного расскажу о утверждении Флориса о том, что при извлечении n бит вам нужно n-1 пространство между любыми непоследовательными битами:

Моя первоначальная мысль (мы увидим через минуту, как это не совсем работает) заключается в том, что вы можете сделать лучше: если вы хотите извлечь n бит, у вас будет столкновение при извлечении / смещении бит i если у вас есть кто-нибудь (не последовательный с битом i ) в битах i-1 предшествующих или последующих бит.

Я приведу несколько примеров для иллюстрации:

...a..b...c... Работает (никто из двух бит после a , бит до и бит после b , и никто не находится в 2 битах до c ):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...ab...c... Сбой, потому что b находится в 2-х битах после (и попадает в чужое место, когда мы сдвигаем a ):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...bc.. работает, потому что b находится в 2 битах, предшествующих c (и попадает в чужое место при смене c ):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... Работает, потому что последовательные биты сдвигаются вместе:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Но у нас есть проблема. Если мы будем использовать ni вместо n-1 мы могли бы иметь следующий сценарий: что, если у нас есть столкновение за пределами той части, о которой мы заботимся, что-то, что мы будем маскировать в конце, но чьи носовые бит в конечном итоге мешают важному не замаскированный диапазон? (и обратите внимание: требование n-1 гарантирует, что этого не произойдет, убедившись, что бит i-1 после того, как наш незамаскированный диапазон станет ясным, когда мы сдвинем i й бит)

...a...b..c...d... Потенциальный сбой на переносных битах, c находится в n-1 после b , но удовлетворяет критериям ni :

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

Так почему бы нам просто не вернуться к требованию « n-1 бит пространства»? Потому что мы можем сделать лучше :

...a....b..c...d.. « n-1 бит пространства», но работает на наш бит-извлекающий трюк:

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

Я не могу придумать хороший способ характеризовать эти поля, у которых нет n-1 пространства между важными битами, но все равно будет работать для нашей работы. Однако, поскольку мы заранее знаем, какие бит нам интересны, мы можем проверить наш фильтр, чтобы убедиться, что мы не сталкиваемся с бит-бит-коллизиями:

Сравнить (-1 AND mask) * shift против ожидаемого результата all-ones, -1 << (64-n) (для 64-битной без знака)

Магический сдвиг / умножение для извлечения наших бит работает тогда и только тогда, когда они равны.





algorithm binary bit-manipulation hammingweight iec10967