Здравствуйте, vsb, Вы писали:

vsb>Кстати утяну с JDK реализацию с помощью битовой арифметики:
vsb>

vsb>    i = i - ((i >>> 1) & 0x55555555);
vsb>    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
vsb>    i = (i + (i >>> 4)) & 0x0f0f0f0f;
vsb>    i = i + (i >>> 8);
vsb>    i = i + (i >>> 16);
vsb>    return i & 0x3f;
vsb>

vsb>Это для 32-битов. Фиг его знает, как оно работает, но, по идее, если не использовать отдельные инструкции процессора, то такой код будет крайне быстр, т.к. это просто последовательность быстрых операций без ветвлений, обращений к памяти и прочей гадости, вжух по регистрам и всё.
Как я понимаю, первая строчка — это немного магии чтобы работать int без поддержки unsigned.
А работает оно просто и красиво. Берём число, например для простоты рассмотрим четырёхразрядное 1110, посчитаем вначале кол-во битов в каждоый группе из двух бит (11)(10). Для этого берём у него нечётные биты и чётные (справа налево): _1_0 и 1_1_ (в коде это наложение битовой маски оператором &). Сдвигаем вторую часть (оператор >>>), получается пара _1_0 и _1_1. Их сумма (оператор +) даёт количество битов в каждой паре _1_0 + _1_1 = (10)(01) т.е. (2 шт)(1 шт). Теперь делаем то же но для групп из четырёх бит: __01 и 10__, сдвигаем получается __01 и __10, складываем: __01 + __10 = 11 т.е. (3 шт). И так постоянно удваивая размер группы можно считать для чисел бОльшей разрядности.