Сообщения

Показаны сообщения с ярлыком "Логарифмы"

Число единичек в двоичном представлении числа

Дано целочисленное число N без знака. Нужно подсчитать количество единичек в его двоичном представлении. Например, число 11 в двоичном представлении выглядит 1011. Значит ответ будет 3. Идея решения: если самый правый бит равен 1, то увеличить счётчик единичек. И в любом случае (0 или 1 справа) сдвинуть битовое представление на 1 позицию вправо, заменяя свободные биты слева нулями. Повторять до тех пор, пока результат сдвига не станет равен нулю. Компилируемый код идеи решения:      int sum=0;         while(N!=0) {             if ((N&1)==1) sum++;             N = N >>> 1;         } Проблема в том, что для больших чисел такой подсчёт может быть непозволительно длинным. Ускорим алгоритм, находя сразу позицию p самого правого ненулевго бита и сдвигая число N на чис...