Наименьшее целое число больше, чем lg N

Question

Я где-то читал, что:

Наименьшее целое число больше lg N количество битов, необходимых для представлять N в двоичном, таким же образом что наименьшее целое число больше log10 N - количество цифр требуется представить N в десятичном виде.

оператор Java

for (lgN = 0; N > 0; lgN++, N /= 2) ; 

- это простой способ вычислить наименьшее целое число больше lg N

Возможно, я что-то здесь упускаю, но как оператор Java вычисляет наименьшее целое число больше lg N?

Answer 1

может быть понятнее, если переписать в цикле while:

lgN = 0
while( N > 0 ) {
    lgN++;
    N = N/2;
}

Что можно считать «сколько раз нам нужно сдвинуть вправо, прежде чем мы сместим все 1» (оставив нам ноль)

Answer 2

Запишите это на бумаге. Пример для N = 1750

   lgN   N      N > 0?
1   0    1750   y
2   1    875    y
3   2    437    y
4   3    218    y
5   4    109    y
6   5    54     y
7   6    27     y
8   7    13     y
9   8    6      y  
10  9    3      y
11  10   1      y
12  11   0      n  stop; lgN = 11

Answer 3

Это ответ на вопрос, который вы должны задать, а именно, как лучше всего вычислить это:

Не делайте этого с помощью цикла. Рассчитайте это напрямую:

int bits = (int) Math.floor(Math.log(n)/Math.log(2)) + 1;

Будьте осторожны, чтобы не позволить n == 0.

Answer 4

Для тех, кто идет по касательной и пытается «остановить безумие петли», предлагая более эффективное решение вопроса, который не был задан, я предлагаю этот способ, который одновременно является более эффективным и читабельным:

 public int bitsNeeded(int n) {
     return 32 - Integer.numberOfLeadingZeros(n);
 }

Как в Javadoc для Integer.numberOfLeadingZeros() сказано:

Обратите внимание, что этот метод тесно связан с основанием логарифма 2. Для всех положительных значений int x:

• floor(log2(x)) = 31 - numberOfLeadingZeros(x)
• ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

Я не публиковал это раньше, поскольку, как я уже сказал, это было тангенциальным. ОП пытался понять цикл, а не найти «лучший» способ что-то сделать.

Answer 5

Похоже, это вычисляет log_2 для N. Так что подумайте с точки зрения двоичного числа, сколько бит требуется, чтобы представить N? Вы узнаете, сколько раз вы можете разделить N на 2 (сдвиньте биты в N на 1 пробел вправо). Сколько раз вы делаете это до того, как N достигнет 0 - это значение, которое вы вычисляете.

Answer 6

Есть какие-либо проблемы, просто отследить это на входе образца?

step 1) N = 10, lgN = 0
step 2) N = 5,  lgN = 1
step 3) N = 2,  lgN = 2
step 4) N = 1,  lgN = 3
step 5) N = 0,  lgN = 4

LGN 4 в конце. Это наименьшее целое число больше log(2, 10)

Answer 7

Это цикл. Его начальным условием является то, что lgN имеет значение ноль. Цикл продолжается до тех пор, пока N больше нуля. На каждой итерации цикла она добавляет единицу к lgN и делит N на 2.

Это очень буквальный перевод того, что делает цикл. Как это работает? Что ж, в первый раз в цикле он увеличивает lgN и делит N на 2. Итак, если N было 1, N теперь равно нулю, и мы закончили. Если N было больше единицы, мы должны повторить снова. Каждый раз, когда вы можете разделить N на 2 без нуля, это еще один обязательный бит в двоичном представлении. Код в основном спрашивает: «Сколько раз я могу разделить N на 2, прежде чем достигну 0?» и это наименьшее целое число больше, чем lg N.

Answer 8

да, для логарифма основания 2 ... (ln N) / (ln 2), а не натурального логарифма

Answer 9

Если все остальное правильно, в коде будет использоваться переменная "lgN", которая существует вне цикла. Когда цикл завершится, ответом будет lgN.

Answer 10

lg N меньше, чем k:

• тогда и только тогда, когда N меньше 2 ^ k
• тогда и только тогда, когда деление N на 2, k раз приводит к 0 (помните, что целочисленное деление округляется в меньшую сторону).

Таким образом, наименьшее целое число, большее, чем lg N, представляет собой число делений на 2, необходимое для достижения 0, и именно это и делает цикл.