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




15 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 .

expressions на русском

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

00000111

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

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




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

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




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



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

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

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




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

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.




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

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

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

    return count;
}



Несколько открытых вопросов: -

  1. Если число отрицательное, то?
  2. Если число равно 1024, то метод «итеративно делить на 2» будет повторяться 10 раз.

мы можем изменить алгоритм для поддержки отрицательного числа следующим образом:

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

теперь, чтобы преодолеть вторую проблему, мы можем написать algo как: -

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

для полной справки см .:

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




Я думаю, что метод Брайана Кернигана тоже будет полезен ... Он проходит через столько итераций, сколько есть битов. Поэтому, если у нас есть 32-битное слово с набором только высоких бит, он будет проходить один раз через цикл.

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

Опубликовано в 1988 году, язык программирования C 2nd Ed. (Брайан У. Керниган и Деннис М. Ричи) упоминает об этом в упражнении 2-9. 19 апреля 2006 года Дон Кнут указал мне, что этот метод «впервые был опубликован Петром Вегнером в CACM 3 (1960), 322. (Также был обнаружен независимо Дерриком Лемером и опубликован в 1964 году в книге под редакцией Беккенбаха)».




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

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

       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-битное значение может быть быстрее.




если вы используете 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 ++, и он в основном просто разворачивает ваш цикл для вас, если для подсчета бит используется постоянное значение (другими словами, я уверен, что это самый быстрый общий метод ты найдешь)




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



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

#include <bits/stdc++.h>

using namespace std;

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



Вот портативный модуль (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



Быстрое решение 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
    };
}



Related