я не думаю, что numberOfLeadingZeros (long i) в Long.java основано floor (log2 (x)) = 63 - numberOfLeadingZeros (x)! - PullRequest
0 голосов
/ 03 марта 2012

это число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), это правда?или, может быть, я настолько глуп, что не могу понять?

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

Ответы [ 2 ]

2 голосов
/ 03 марта 2012

Количество цифр в номере равно 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 битов и последнего бита.

0 голосов
/ 03 марта 2012

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

...