Вычисление суммы битов в целом числе

Несколько лет назад в одном проекте на Java встала задача написать функцию вычисления суммы битов в целом числе типа long (в Java типу long соответствует целое 64-битное число).

Простое решение

Copy Source | Copy HTML

1. public int getBitsSum(final long a) {
2.     int sum =  0;
3.     for(long b = 1; b !=  0; b <<= 1) {
4.         if ((a & b) !=  0) sum++;
5.     }
6.     return sum;
7. }

оказалось слишком медленным.

Потом пришла в голову идея перейти от скалярных вычислений (то есть побитовых) к векторным, когда операции совершаются сразу над несколькими битами. Для этого биты числа а представим в виде 64-мерного вектора. Затем этот вектор разделим на два 32-мерных вектора: в первый вектор перепишем все координаты с четными номерами, а во второй с нечетными. Два полученных вектора сложим. В результате получим 32-мерный вектор, каждая координата которого равна сумме соседних битов исходного числа.

На втором шаге вектор, полученный после первого шага, аналогично разделим на два 16-мерных вектора и сложим их. В результате получим 16-мерный вектор каждая координата которого равна сумме четверки соседних битов исходного числа a.

Проведя такую операцию еще всего 4 раза получим одномерный вектор, координата которого будет равна сумме всех битов исходного числа.

Далее обратим внимание на то, что сумма двух n-битных чисел не может занимать более 2n битов (на самом деле, она занимает не более n+1 бита). Следовательно, требуемое сложение векторов можно реализовать в виде сложения 64-битных чисел, если между координатами вставить достаточное число нулевых битов.

На рисунке приведен пример работы алгоритма для случая 8-битного числа.


В результате дальнейшей (уже безыдейной) оптимизации была получена функция

Copy Source | Copy HTML

1. public int getBitsSum(final long a) {
2.     int lo = (int) a;
3.     lo -= ((lo >> 1) & 0x55555555);
4.     lo = (lo & 0x33333333) + ((lo >> 2) & 0x33333333);
5.     int hi = (int) (a >> 32);
6.     hi -= ((hi >> 1) & 0x55555555);
7.     hi = (hi & 0x33333333) + ((hi >> 2) & 0x33333333);
8.     hi += lo;
9.     hi = (hi & 0x0F0F0F0F) + ((hi >> 4) & 0x0F0F0F0F);
10.     hi += (hi >> 16);
11.     return (hi + (hi >> 8)) & 0x000000FF;
12. }

Замечание. Как ни странно, но функция

Copy Source | Copy HTML

1. public int getBitsSum(long a) {
2.     a -= ((a >> 1) & 0x5555555555555555L);
3.     a = (a & 0x3333333333333333L) + ((a >> 2) & 0x3333333333333333L);
4.     a = (a & 0x0F0F0F0F0F0F0F0FL) + ((a >> 4) & 0x0F0F0F0F0F0F0F0FL);
5.     a += (a >> 8);
6.     a += (a >> 16);
7.     a += (a >> 32);
8.     return (int) (a & 0x00000000000000FFL);
9. }

на 64-битной платформе (Vista x64 + Java 1.6.0_20 x64) работает медленней. Видимо причина в том, что она хуже укладывается в конвеер процессора.

Можно ли вычислить сумму битов на Java быстрее?