Но вряд ли кто-то в реальной жизни будет считать число единиц в бинарном представлении целого числа на Perl. Много ли Вы вообще знаете задач, где актуальна проблема подсчета количества единиц? Это очень, очень редкие и специфические алгоритмы, самые что ни на есть "ядерные" - к оболочке и скриптам отношения (я думаю) не имеющие. Причем может оказаться, что единицы нужно считать даже не в отдельных числах, а в массивах, и тогда потребуются еще более изощренные вариации алгоритма. Или даже особые структуры данных – например, если нужно считать расстояния по Хеммингу между миллионами битовых векторов. При написании такого "ядерного" кода может оказаться полезным учесть и плотность единиц - например, если ожидается, что они очень редки - использовать цикл, если их сравнительно много - код типа рассмотренного в этой ветке, если процессор имеет соответствующую команду (x86 SSE 4.2, Power5+, Itanium, Alpha EV6+) – то использовать ее...
Да, это известно - но написание таких шаблонов (с циклами) очень сложная задача и они замедляют работу компилятора, поэтому разработчики GCC пошли по пути добавления встроенной функции __builtin_popcount вместо описания новых преобразований в промежуточном языке.
В свою очередь для программиста это приводит к тому, что приходится писать generic код на plain C типа приведенного Вами под все процессоры, плюс к этому еще и проверять версию GCC на 3.4 и тогда использовать __builtin_popcount. А для старых версий GCC и для других компиляторов приходится использовать вручную написанные ассемблерные вставки или другие builtin функции.
Разумеется, я имею в виду ситуацию, когда кому-то нужно экстраординарное быстродействие при подсчете числа единиц в числе.
При тестировании таких фрагментов важно принимать во внимание конечную цель - зачем этот код используется и что подается ему на вход. Вариант с "x & (x - 1)" хорош тогда и только тогда, когда в числе маленькое количество единиц. В Вашем тесте разницу можно увидеть, если убрать "тяжелые" шаблоны из теста, такие, как 255, 1023 и особенно 0x33333333,0xFFFF0000 и 0xFFFFFFFF. Для них лучшее решение - это вариации . И конечно же самое главное - эти коды не для скриптовых языков (типа perl). Понятное дело, что при использовании perl встроенная функция обгонит все, так как основные накладные расходы в реально хороших вариантах идут на синтаксический анализ и интерпретацию.
Еще можно добавить вариант для 64-х битной машины без сверхбыстрого умножения:
uint get_ones_count(uint64_t x) {
uint64_t n;
n = (x >> 1) & 0x7777777777777777;
x = x - n;
n = (n >> 1) & 0x7777777777777777;
x = x - n;
n = (n >> 1) & 0x7777777777777777;
x = x - n;
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return (uint) (x & 0xFF);
}
Ну, наверное, если кто-то пишет такой код - значит ему не пофик, сколько времени будет выполняться его программа. И не надо говорить мне, что, дескать, быстродействие кода давно и абсолютно никого не волнует. Если бы быстродействие никого не волновало, то в новые варианты PowerPC и Intel не добавили бы машинную команду для этого самого подсчета количества единиц. Вера во всемогущество компилятора тоже ни на чем не основана – простой подсчет количества единиц (записанный через тупой цикл) компилятор ни на этот код, ни на использование одной машинной команды САМ не заменит, он ведь искусственным интеллектом не обладает (пока что, во всяком случае).
В таком виде код понятен и легко читается, то есть, он ВНЕШНЕ красиво смотрится. Но как тут верно заметили - для реального проекта этот код недоделанный:
- Нужно использовать беззнаковые целые,
- Следует отвязаться от 32-битной разрядности обычного int и добавить вариант для 64-битных процессоров (который будет иметь несколько иной код, чтобы избежать массового использования длинных целых констант),
- Этот код не оптимизирован и для 32-битной платформы, в нем можно переписать известным образом (с использованием вычитания) первый шаг алгоритма и последние шаги избавить от лишнего маскирования,
- Возможны оптимизации через использование умножения для некоторых архитектур,
- В программе так же хорошо бы предусмотреть подмену этой функции на ассемблерные вставки для конкретных современных процессоров (их новых модификаций), учитывая, что почти все из них (включая последние варианты Intel x86) имеют аппаратную команду для подсчета количества единиц в числе. Если такой код пишется - значит гонятся за быстродействием, а раз так - сам Бог велел использовать аппаратное ускорение возможное на конкретных CPU. :)
В свою очередь для программиста это приводит к тому, что приходится писать generic код на plain C типа приведенного Вами под все процессоры, плюс к этому еще и проверять версию GCC на 3.4 и тогда использовать __builtin_popcount. А для старых версий GCC и для других компиляторов приходится использовать вручную написанные ассемблерные вставки или другие builtin функции.
Разумеется, я имею в виду ситуацию, когда кому-то нужно экстраординарное быстродействие при подсчете числа единиц в числе.
uint get_ones_count(uint64_t x) {
uint64_t n;
n = (x >> 1) & 0x7777777777777777;
x = x - n;
n = (n >> 1) & 0x7777777777777777;
x = x - n;
n = (n >> 1) & 0x7777777777777777;
x = x - n;
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return (uint) (x & 0xFF);
}
с = 0;
while (x) {
c = c + 1;
x = x & (x - 1);
}
кстати в некоторых случаях этот вариант еще и самый быстрый.
- Нужно использовать беззнаковые целые,
- Следует отвязаться от 32-битной разрядности обычного int и добавить вариант для 64-битных процессоров (который будет иметь несколько иной код, чтобы избежать массового использования длинных целых констант),
- Этот код не оптимизирован и для 32-битной платформы, в нем можно переписать известным образом (с использованием вычитания) первый шаг алгоритма и последние шаги избавить от лишнего маскирования,
- Возможны оптимизации через использование умножения для некоторых архитектур,
- В программе так же хорошо бы предусмотреть подмену этой функции на ассемблерные вставки для конкретных современных процессоров (их новых модификаций), учитывая, что почти все из них (включая последние варианты Intel x86) имеют аппаратную команду для подсчета количества единиц в числе. Если такой код пишется - значит гонятся за быстродействием, а раз так - сам Бог велел использовать аппаратное ускорение возможное на конкретных CPU. :)