Алгоритмы и структуры данных: продвинутый уровень Количество единичек в двоичном представлении числа
Выпуск 6. Количество единичек в двоичном представлении числа
Здравствуйте, !
Дано целочисленное число N без знака. Нужно подсчитать количество единичек в его двоичном представлении.
Например, число 11 в двоичном представлении выглядит 1011. Значит ответ будет 3.
Идея решения: если самый правый бит равен 1, то увеличить счётчик
единичек. И в любом случае (0 или 1 справа) сдвинуть битовое
представление на 1 позицию вправо, заменяя свободные биты слева нулями.
Повторять до тех пор, пока результат сдвига не станет равен нулю.
Компилируемый код идеи решения:
int sum=0;
while(N!=0) {
if ((N&1)==1) sum++;
N = N >>> 1;
}
Проблема в том, что для больших чисел такой подсчёт может быть непозволительно длинным.
Ускорим алгоритм, находя сразу позицию p самого правого ненулевго бита и сдвигая число N на число позиций p:
int sum = 0;
while (N!=0) {
double position = 1 + Math.log(N & ~(N-1))/Math.log(2);
if (position!=0) sum++;
n >>>= (int)position;
}
return sum;
Поясним метод подсчёта position. Возьмём N=28.
Его двоичное представление = 11100. Это число X.
Двоичное представление 28-1=27 будет : 11011
Двоичное представление ~27 (инвертирование всех битов) : 00100
(с единичками впереди 11111111111111111111111111100100) Это
число Y.
И подсчитав побитово X&Y мы получим : 100 в двоичной системе. Или 4 в десятичной.
Разложение 4 в двоичную систему происходит по фомуле 1*2^2 + 0*2^1 + 0*2^0. Или 4 = 2^2. (Z)
Если прологарифмировать обе части по основанию 2, то равенство Z сохранится: log2(4) = log2(2^2).
Пользуясь свойством степени в логарифме: log2(2^2)=2*log2(2).
А log2(2)=1. Поэтому в итоге log2(4)=2. Это на 1 меньше, чем ожидаемоая позиция 3. Поэтому добаляем +1.
Проблема в том, что в библиотеке Java нет двоичного логарифма, а есть только натуральный.
Но у логарифма есть свойства log2(a) = logn(a)/logn(2).
Поэтому в итоге подсчёт значения position сводится к тому, что:
мы подсчитываем число Q=N & ~(N-1), которое начинается с самого правого бита исходного N;
число Q мы логарифмируем, по основанию 2: log(Q)/log(2);
увеличиваем Math.log(Q)/Math.log(2)+1, чтобы получить ожидаемую позицию position;
если position==1, то увеличиваем счётчик;
наконец, сдвигаем число N на position битов вправо (аналог деления на 2 position раз).
Запомнить:
формула для получения двоичного представления, в котором включен только самый правый бит исходного числа N & ~(N-1)
формула позиции самого правого бита: 1 + Math.log(N & ~(N-1))/Math.log(2)
С уважением, Наталия Македа natalia.macheda at gmail.com 2021-03-23, Trento
Внимание! Письмо, которое вы мне отправите с вопросами и коментариями по тематике данной рассылки, может быть опубликовано полностью или частично в данной рассылке, если в нём нет явного запрета на это.
