C-код для подсчета количества битов «1» в неподписанном символе

Question

Мне нужен код C, чтобы вернуть число 1 в беззнаковом символе в C. Мне нужно объяснение, почему это работает, если это не очевидно. Я нашел много кода для 32-битного числа, но не много для беззнакового символа.

Answer 1

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

Иметь массив, который знает количество битов от 0 до 15. Добавьте результаты для каждого куска.

Answer 2

Тот же код будет работать для неподписанного символа. Переберите все биты, проверяя их. Смотрите это .

Answer 3

HACKMEM имеет этот алгоритм в 3 операциях (грубо переводится в C):

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

(ULL - форсировать 64-битную арифметику. Это нужно, просто ... для вычисления требуется 33-битное целое число.)

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

Как это работает? Подумайте о c побитовым образом и помните, что (a + b) % c = (a % c + b % c) % c и (a | b) == a + b тогда и только (a & b) == 0.

  (c * 01001001001ULL & 042104210421ULL) % 017
  01   01001001001                01         1
  02   02002002002       02000000000         1
  04   04004004004          04000000         1
 010  010010010010            010000         1
 020  020020020020               020         1
 040  040040040040      040000000000         1  # 040000000000 == 2 ** 32
0100 0100100100100        0100000000         1
0200 0200200200200           0200000         1

Если у вас нет 64-битной арифметики, вы можете разделить c на кусочки и делать каждую половину, выполняя 9 операций. Для этого требуется всего 13 бит, поэтому сработает 16- или 32-битная арифметика.

bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;

(c * 0421 & 01111) % 7
 1   0421      01    1
 2  01042   01000    1
 4  02104    0100    1
 8  04210     010    1

Например, если c == 105 == 0b11001001,

c == 0100
   |  040
   |  010
   |   01 == 0151
* 01001001001001ULL == 0100100100100
                     |  040040040040
                     |  010010010010
                     |   01001001001 == 0151151151151
& 0421042104210421ULL ==  0100000000
                       | 04000000000
                       |      010000
                       |          01 ==   04100010001
% 017                                == 4

c & 017      ==            8 | 1           ==                   011
011 * 0421   ==     8 * 0421 | 1 * 0421    == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 ==   010 | 01   ==   011
011 % 7      == 2

c >> 4       ==            4 | 2            ==                     06
06 * 0421    ==     4 * 0421 | 2 * 0421     == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 ==  0100 | 01000 == 01100
01100 % 7    == 2

2 + 2 == 4

Answer 4

См. Страницу битовых хищных взломов: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Есть много хороших решений для этого.

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

Answer 5

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

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

Эта техника называется SWAR (http://en.wikipedia.org/wiki/SWAR).

Для получения дополнительной информации я предлагаю вам посетить веб-сайт восхищения хакеров: www.hackersdelight.org. У него есть пример кода и он написал книгу, которая подробно объясняет эти приемы.

Answer 6

основано на посте Ephemient, у нас есть 8-битная версия без разветвлений. В шестнадцатеричном выражении.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

Примените его дважды, у нас есть 16-битная версия, которая требует 9 операций.

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

Здесь я пишу вариант 16-битной версии, которая требует 64-битных регистров и 11 операций. Кажется, он не лучше предыдущего, но он использует только 1 операцию по модулю.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}

Answer 7

Как уже ответили, стандартные способы подсчета битов также работают с неподписанными символами.

Пример:

    unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
    if ( value & 1 == 1 ) 
        bitCount++;
    value >>= 1;
}

Answer 8

беззнаковый символ является «числом» точно так же, как 32-разрядное число с плавающей точкой или целое число является «числом», и то, что компилятор считает, что они представляют, является тем, что изменяется.

если вы представляете символ как его биты:

01010011 (8 бит);

Вы можете посчитать установленные биты, выполнив следующее:

принять значение, допустим, x и принять x% 2, остаток будет либо 1, либо 0. То есть, в зависимости от порядкового номера символа, самый левый или правый бит. накапливать остаток в отдельной переменной (это будет итоговое количество установленных бит).

затем >> (сдвиг вправо) 1 бит.

повторять до тех пор, пока 8 бит не будут сдвинуты.

код c должен быть довольно простым для реализации из моего псевдокода, но в основном

public static int CountSetBits(char c)
{
    int x = 0;
    int setBits = 0;
    while (x < 7)
    {
       setBits = setBits + c % 2;
       c = c >> 1;
       x = x + 1;
    }
}