Метод Quickest / Shortest в C / C ++ для вычисления суммы цифр в двоичном коде / он же число 1 в двоичном
Мне нравится находить кратчайшие методы кодирования. Я обнаружил необходимость в методе вычисления суммы цифр (или числа 1 в числе) числа, представленного в двоичном виде. Я использовал битовые операторы и нашел это:
r=1;while(a&=a-1)r++;
где а это число, а р это количество. а является заданным целым числом. Есть ли способ сократить / улучшить алгоритм?
Наименьший как в самой короткой длине исходного кода.
Решение
Ваше решение предполагает a иметь неподписанный тип.
Тем не менее код не работает для a = 0, Вы можете исправить это так:
r=!!a;while(a&=a-1)r++;
Вы можете сбрить одного персонажа таким образом:
for(r=!!a;a&=a-1;r++);
Но вот альтернативное решение с той же длиной источника:
for(r=0;a;a/=2)r+=a&1;
Как упоминал Лундин, игра в гольф с кодами не входит в тему переполнения стека. Это забавная игра, и можно определенно оттачивать его навыки C, пытаясь создать наименьший код, который все еще полностью определен для данной проблемы, но полученный код имеет низкую ценность для случайных читателей, пытающихся программировать на более базовом уровне. ,
Что касается тематической части вашего вопроса, Самый быстрый метод для вычисления количества бит в целом числе: эта проблема интенсивно изучается и доступны несколько методов. Какой из них самый быстрый, зависит от многих факторов:
- насколько переносимым должен быть код. Некоторые процессоры имеют встроенные инструкции для этого, и компилятор может предоставить способ их генерирования с помощью встроенных или встроенных сборок.
- ожидаемый диапазон значений для аргумента. Если диапазон небольшой, простая справочная таблица может дать лучшую производительность.
- Распределение значений аргумента: если конкретное значение дается почти всегда, просто проверка его может быть самым быстрым решением.
- специфическая производительность процессора: разные алгоритмы используют разные инструкции, относительная производительность разных процессоров может отличаться.
Только тщательный сравнительный анализ покажет вам, является ли данный подход предпочтительным по сравнению с другим, или если вы пытаетесь оптимизировать код, производительность которого не имеет значения. Допустимая корректность много важнее микрооптимизации. Многие эксперты считают, что оптимизация всегда преждевременна.
Интересное решение для 32-битных целых чисел заключается в следующем:
uint32_t bitcount_parallel(uint32_t v) {
uint32_t c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
return ((c >> 16) + c) & 0x0000FFFF;
}
Если умножение быстро, вот потенциально более быстрое решение:
uint32_t bitcount_hybrid(uint32_t v) {
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
Различные решения подробно описаны здесь: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
Другие решения
Самый быстрый код — это создание справочной таблицы со значением переменной в качестве индекса. Пример для uint8_t:
const uint8_t NUMBER_OF_ONES [256] =
{
0, // 0
1, // 1
1, // 2
2, // 3
1, // 4
2, // 5
...
8, // 255
};
Вы бы использовали его как n = NUMBER_OF_ONES[a];,
Вторым быстрым является создание меньших справочных таблиц для сохранения ПЗУ. Например, поиск по частям от 0 до 15, который вы затем вызываете для каждого куска в типе данных.
Обратите внимание, что требование «Наименьший как наименьшая длина исходного кода». ерунда, это не показатель, используемый профессионалами. Если это действительно то, что вам нужно, ради забавы или запутывания, тогда вопрос не по теме на SO, и его следует задать на https://codegolf.stackexchange.com вместо.