AM
В моем алгоритме если у тебя только старший бит 1
Size: a a a
2020 June 10
AM
будет 1 операция
AM
а в твоем 32
AM
Порядок сложности одинаковый
AM
(n » i) & 1
Ну давай проверим
AM
есть число в бинарном представлении
AM
1000 0000 0000 0000
AM
сколько операций сделает твой алгоритм?
AM
Мой сделает ровно одну
AM
он сделает И c числом 0111 1111 1111 1111
AM
прибавит счетчик и дойдет до 0 выйдя из цикла
AM
а твой будет сдвигать каждый бит
AM
и проверять а ноль ли там или 1
LV
уговорил, неплохо
так что мое выражение обозначало?
AM
Но в Java юзается математический метод
AM
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
AM
который я ебал понимать