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

-
Дано целочисленное число 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 сводится к тому, что:
  1. мы подсчитываем число Q, которое начинается с самого правого бита исходного N.
  2. число Q мы логарифмируем, по основанию 2, чтобы подсчитать position.
  3. для того, чтобы получить основание 2, мы делаем Math.log(Q)/Math.log(2)+1.
Запомнить: 
  • формула для получения двоичного представления, в котором включен только самый правый бит исходного числа N & ~(N-1)
  • формула позиции самого правого бита: 1 + Math.log(N & ~(N-1))/Math.log(2)

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

-
Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...
Далее...

Число подмассивов, в которых сумма элементов равна k

-
Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...
Далее...

Сложить два числа, которые представлены списком

-
Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка. Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0. Пример: Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4) Резальтат: 7 -> 0 -> 8 Пояснение: 342 + 465 = 807. Идея решения. В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик. Имплементация. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка     ListNode p = l1, q = l2, curr = dummyHead;     int carry = 0;     while (p != null || q != null) {         int x = (p != null) ? p.v...
Далее...