Понимание логики реализации метода Integer.highestOneBit () - PullRequest
Новая
       9

Понимание логики реализации метода Integer.highestOneBit ()

0 голосов
/ 19 ноября 2018

Класс Java Integer имеет метод staticOneBit статического метода, который будет возвращать значение с одним однобитным в позиции однобитового старшего разряда в указанном значении или ноль, если указанное значение само по себе равноноль.

Например, ввод int 17 вернет 16;Поскольку 17 можно представить в двоичном виде как 10001, поэтому он вернет самый дальний оставшийся бит, равный 16.

И в классе Integer он имеет следующую реализацию в Java doc. 

    public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

Я просто хочу знать логику реализации этого способа и логику использования операций сдвига.Может ли кто-нибудь пролить свет на это.

Ответы [ 3 ]

0 голосов
/ 19 ноября 2018

Операторы i |= помогают вычислить последовательность единиц, которая имеет ту же длину, что и i.Например, для 101011 он вычисляет 111111.Я объяснил, как это работает в этом ответе (я не могу набрать его прямо сейчас, так как я нахожусь на мобильном телефоне).

Так что, в принципе, когда у вас есть строка из них, вычитаяСам сдвиг вправо на один бит дает бит HO. 

111111 - (111111 >>> 1) = 111111 - 011111 = 100000
0 голосов
/ 19 ноября 2018

Первые пять строк (i |= (i >> x)) будут устанавливать каждый бит ниже старшего 1-битного значения в 1. Затем, последняя строка будет вычитать каждый 1-бит ниже старшего, так что только самый старший 1-битный будетостаются.

Для простоты давайте представим, что int было 8 бит.Код в этом случае будет выглядеть следующим образом: 

public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    return i - (i >>> 1);
}

Теперь предположим, что у нас есть значение 128 (10000000).Вот что произойдет: 

// i == 10000000
i |= (i >>  1); // i = 10000000 | 11000000 = 11000000 
i |= (i >>  2); // i = 11000000 | 11110000 = 11110000 
i |= (i >>  4); // i = 11110000 | 11111111 = 11111111
return i - (i >>> 1); // 11111111 - 01111111 = 10000000

>> - это арифметическое смещение вправо, поэтому он сохранит бит со знаком.Последний >>> - это логический сдвиг вправо, который не сохранит бит со знаком.Он всегда будет вставлять нули с левой стороны.

Теперь давайте попробуем с 64 (01000000): 

// i == 01000000
i |= (i >>  1); // i = 01000000 | 00100000 = 01100000 
i |= (i >>  2); // i = 01100000 | 00011000 = 01111000 
i |= (i >>  4); // i = 01111000 | 00000111 = 01111111
return i - (i >>> 1); // 01111111 - 00111111 = 01000000
0 голосов
/ 19 ноября 2018

Этот алгоритм вычисляет для заданного i, чье двоичное представление: 

0..01XXXXXXX...XXXX

значение 

0..011111111...1111

Это то, что делают операторы 5 |=.

Затем в операторе возврата вычитается, что значение сдвинуто вправо на один бит 

0..001111111...1111

чтобы получить результат 

0..010000000...0000

Как это работает:

Максимально возможный 1 бит 32-й (самый левый) бит. Предположим, что входной номер имеет 1 в этом бите: 

1XXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

Вы или это значение со смещением вправо на 1 (i >> 1) и получите 

11XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

Тогда вы или это новое значение со значением, сдвинутым вправо на 2 (i >> 2), и получите 

1111XXXX XXXXXXXX XXXXXXXX XXXXXXXX

Тогда вы или это новое значение со значением, сдвинутым вправо на 4 (i >> 4), и получите 

11111111 XXXXXXXX XXXXXXXX XXXXXXXX

Тогда вы или это новое значение со значением, сдвинутым вправо на 8 (i >> 8), и получите 

11111111 11111111 XXXXXXXX XXXXXXXX

Наконец, вы или это новое значение со значением, сдвинутым вправо на 16 (i >> 16), и получите 

11111111 11111111 11111111 11111111

Если старший 1 бит меньше 32-го, эти операции по-прежнему переводят все биты справа от него в 1 и сохраняют оставшиеся (старшие биты) 0.

...