я не думаю, что numberOfLeadingZeros (long i) в Long.java основано floor (log2 (x)) = 63 - numberOfLeadingZeros (x)!

Question

это числоOfLeadingZeros (long i) в Long.java:

public static int numberOfLeadingZeros(long i) {
        // HD, Figure 5-6
         if (i == 0)
            return 64;
        int n = 1;
        int x = (int)(i >>> 32);
        if (x == 0) { n += 32; x = (int)i; }
        if (x >>> 16 == 0) { n += 16; x <<= 16; }
        if (x >>> 24 == 0) { n +=  8; x <<=  8; }
        if (x >>> 28 == 0) { n +=  4; x <<=  4; }
        if (x >>> 30 == 0) { n +=  2; x <<=  2; }
        n -= x >>> 31;
        return n;
}

, и автор сказал, что это base floor (log2 (x)) = 63 - numberOfLeadingZeros (x) или ceil (log2(x)) = 64 - numberOfLeadingZeros (x - 1), это правда?или, может быть, я настолько глуп, что не могу понять?

кто-то, кто может мне это объяснить?спасибо!

Answer 1

Количество цифр в номере равно floor(log(num)) + 1 (с логином в правильной базе.) Если общее число цифр равно x, то число ведущих нулей равно

x - (floor(log(num)) + 1) =
(x - 1) - floor(log(num))

Так что в вашемрегистр с 64 цифрами и двоичным числом

leadingZeros(num) = 63 - floor(log_2(num))

Редактировать:

>>> является оператором смещения вправо без знака в Java, а << являетсясдвиг влево.n >>> 32 сместит n 32 бита вправо при заполнении пустого пространства нулями.

Таким образом, алгоритм работает следующим образом:

0000000000000000000000000000000000000000000001011010100000101011

1. Shifti 32 бита справа, поэтому x содержит только старшие 32 бита.

   00000000000000000000000000000000

2. Если (a) это 0, мы знаемстаршие 32 бита были равны 0, поэтому добавьте 32 к начальному нулю и сконцентрируйтесь на младших 32 битах.(b) В противном случае это ненулевое значение, поэтому число имеет менее 32 ведущих нулей.Сконцентрируйтесь на верхних 32 битах.

3. Сдвиг x 16 бит вправо.

   0000000000000101

   Таким же образом: (a) Если это 0, прибавьте 16 к счетчику начальных нулей и сконцентрируйтесь на следующих младших 16 битах (сдвинув их влево в область, где мы работаем.) (b) Если это ненулевое значение, то у нас меньше16 ведущих нулей для добавления.

4. Повторите для следующего байта, затем для следующих 4 битов, 2 битов и последнего бита.

Answer 2

Да, это правда, при условии, что вы просматриваете x как число без знака.