Код C для подсчета количества битов '1' в символе без знака

Question

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

Answer 1

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

Answer 2

родовое слово

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

Answer 3

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

родовое слово

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

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

Как это работает?Подумайте о генерации кодового кода побитовым образом и запомните, что генерирует кодовый код, а генерирует кодовый код, если и только генерирует кодовый код.

родовое слово

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

родовое слово

Например, если генерирует код кода,

родовое слово

Answer 4

См. страницу с хитростями: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

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

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

Answer 5

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

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

Этот метод называется SWAR ( http://en.wikipedia.org/wiki/SWAR).

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

Answer 6

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

Пример:

родовое слово

Answer 7

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

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

01010011 (8 бит);

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

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

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

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

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

родовое слово

Answer 8

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

родовое слово

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

родовое слово

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

родовое слово