HashMap.tableSizeFor (...). Как этот код округляется до следующей степени 2? - PullRequest
Новая
       9

HashMap.tableSizeFor (...). Как этот код округляется до следующей степени 2?

0 голосов
/ 30 июня 2018

Пожалуйста, опишите, что делают эти n| = n >>> x 5 строк?

Меня не интересует, что делают операторы | или >>>. Мне интересно, что эта сложная логика делает под прикрытием на математическом языке. 

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Ответы [ 2 ]

0 голосов
/ 01 июля 2018

У всех (положительных) степеней двух установлен ровно 1 бит; и (степень 2 - 1) имеет все биты, установленные меньше, чем старший значащий бит. Итак, мы можем найти следующую по величине степень двойки к

  • Вычитание 1
  • Установка всех младших битов
  • Добавление 1 назад

Эти операции сдвига битов реализуют второй этап этого процесса, «размазывая» установленные биты.

Итак: 

n |= n >>> 1;

будет делать что-то вроде: 

  01010000
| 00101000
= 01111000

Если вы сделаете это снова, вы снова «размажете» номер (все еще сдвигаясь всего на 1): 

  01111000
| 00111100
= 01111100

Продолжайте делать это, и в результате вы получите число со всеми менее значимыми битами: 

01111111

В худшем случае вам придется делать это 30 раз (для положительного 32-разрядного целого числа со знаком), когда самый старший бит - это 31-й бит: 

   01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 0111xxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 01111xxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011111xxxxxxxxxxxxxxxxxxxxxxxxxx
...
=> 01111111111111111111111111111111

(x просто означает, что это может быть ноль или единица)

Но вы можете заметить кое-что интересное: после первого мазка, при сдвиге на 1, у нас установлены два старших значащих бита. Таким образом, вместо сдвига на 1, мы можем пропустить операцию, сдвинув на 2: 

   01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 01111xxxxxxxxxxxxxxxxxxxxxxxxxxx

Продолжая эту схему, сдвиньте на 4 затем: 

=> 011111111xxxxxxxxxxxxxxxxxxxxxxx

Сдвиг на 8: 

=> 01111111111111111xxxxxxxxxxxxxxx

Сдвиг на 16: 

=> 01111111111111111111111111111111

Итак, вместо 30 операций, чтобы установить все менее значимые биты, мы взяли 5.

0 голосов
/ 01 июля 2018

Чтобы понять процесс, давайте предположим, что значение пройденного предела равно 10.

То есть n = capacity - 1 = 9; 0000 1001

n |= n >>> 1   = 0000 1101
n |= n >>> 2   = 0000 1111
n |= n >>> 4   = 0000 1111
n |= n >>> 8   = 0000 1111
n |= n >>> 16  = 0000 1111 = 15

Наконец метод возвращает n + 1 = 16

Для больших чисел 

cap           = 0000 1000 0000 0000 0000 0000 0000 0001
n = cap - 1   = 0000 1000 0000 0000 0000 0000 0000 0000
n |= n >>> 1  = 0000 1100 0000 0000 0000 0000 0000 0000
n |= n >>> 2  = 0000 1111 0000 0000 0000 0000 0000 0000
n |= n >>> 4  = 0000 1111 1111 0000 0000 0000 0000 0000
n |= n >>> 8  = 0000 1111 1111 1111 1111 0000 0000 0000
n |= n >>> 16 = 0000 1111 1111 1111 1111 1111 1111 1111
return n + 1  = 0001 0000 0000 0000 0000 0000 0000 0000
...