Мне нужен код C, чтобы вернуть количество единиц в беззнаковом символе в C. Мне нужно объяснение, почему это работает, если это не очевидно. Я нашел много кода для 32-битного числа, но не так много для беззнакового символа.
Код C для подсчета количества битов «1» в беззнаковом символе
Ответы (8)
Тот же код будет работать для беззнакового символа. Перебрать все биты, проверяя их. См. это.
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. Добавьте результаты для каждого полубайта.
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
См. страницу хаков с битами: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
для этого есть много хороших решений.
Кроме того, эта функция в простейшей реализации довольно тривиальна. Вы должны найти время, чтобы узнать, как это сделать.
Для целого числа размером с беззнаковый символ вы получаете лучшую производительность, используя небольшую таблицу поиска.
Я знаю, о каких алгоритмах подсчета населения вы говорите. Они работают, выполняя арифметические действия над несколькими словами, меньшими, чем целое число, хранящееся в регистре.
Этот метод называется SWAR (http://en.wikipedia.org/wiki/SWAR). .
Для получения дополнительной информации я предлагаю вам посетить веб-сайт хакерского восторга: www.hackersdelight.org. У него есть пример кода, и он написал книгу, в которой подробно объясняются эти трюки.
Как уже было сказано, стандартные способы подсчета битов также работают с беззнаковыми символами.
Пример:
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
unsigned char - это "число" точно так же, как 32-битное число с плавающей запятой или целое число является "числом", то, что компилятор считает, что они представляют, - это то, что меняется.
если вы представляете char как его биты:
01010011 (8 бит);
вы можете подсчитать установленные биты, выполнив следующие действия:
возьмите значение, скажем, x, и возьмите x% 2, остаток будет либо 1, либо 0. то есть, в зависимости от порядка байтов char, самый левый или правый бит. накапливаем остаток в отдельной переменной (это будет результирующее количество установленных битов).
затем >> (правый сдвиг) 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;
}
}
основываясь на сообщении 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);
}