Как (я << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (я >>> 48) работаешь? - PullRequest
Новая
       27

Как (я << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (я >>> 48) работаешь?

6 голосов
/ 02 марта 2012

Вот реализация обратного в Long: 

public static long reverse(long i) {
        // HD, Figure 7-1
    i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;//1
    i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;//2
    i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;//3
    i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;//4
    i = (i << 48) | ((i & 0xffff0000L) << 16) |
        ((i >>> 16) & 0xffff0000L) | (i >>> 48);//5
    return i;
}

Я могу понять строку 1,2,3,4, но не 5!Как это работает?

Я группирую 64 бита в 8 групп, то есть 1 - первые 8 бит, 2 - вторые 8 бит и т. Д.

Затем после строки 4последовательность вроде 4,3,2,1,8,7,6,5

, и я думаю, что строка 5 работает, как показано ниже, до операции |: 

6,5,0,0,0,0,0,0-->(i << 48)
8,7,0,0,0,0,0,0-->((i & 0xffff0000L) << 16)
0,0,0,0,4,3,2,1-->((i >>> 16) & 0xffff0000L)
0,0,0,0,0,0,2,1-->(i >>> 48)

Но я не знаю, где это неправильно или нетэто неверно!Думая об этом почти целый день!

Кто-нибудь может мне помочь !!Спасибо.

о, я допустил такую ​​ошибку: 

6,5,0,0,0,0,0,0-->(i << 48)
0,0,8,7,0,0,0,0-->((i & 0xffff0000L) << 16)
0,0,0,0,2,1,0,0-->((i >>> 16) & 0xffff0000L)
0,0,0,0,0,0,4,3-->(i >>> 48)

но я думаю, что это неправильно!Я думаю, правильная последовательность: 8,7,6,5,4,3,2,1

Мне очень жаль, что я допустил некоторые ошибки!он работает так, как показано ниже:

после строки 4, правильный шаблон: 2,1,4,3,6,5,8,7

8,7,0,0,0,0,0,0-->(i << 48)
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16)
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L)
0,0,0,0,0,0,2,1-->(i >>> 48)

Ответы [ 2 ]

7 голосов
/ 02 марта 2012

Строка 1 меняет местами соседние одиночные биты (0 <-> 1; 2 <-> 3; и т. Д.). Строки 2-4 меняют местами смежные последовательности из двух битов, 4 битов и 8 битов. В этот момент исходное значение было преобразовано в четыре блока по 16 битов, причем каждый блок был обратным тому, что было в начале. Строка 5 затем переставляет 4 блока. По сути, строка 5 объединяет два шага в один: замена двух пар 16-битных блоков и замена одной пары 32-битных блоков. Логика:

  • (i << 48) перемещает самый правый 16-битный блок в левую позицию, оставляя все остальные биты равными нулю
  • ((i & 0xffff0000L) << 16) перемещает второй блок справа на второй блок слева (все остальные биты ноль)
  • ((i >>> 16) & 0xffff0000L) перемещает второй блок слева на второй блок справа (все остальные биты равны нулю)
  • (i >>> 48) перемещает крайний левый блок в правую позицию (все остальные биты равны нулю)

Затем эти четыре значения | соединяются вместе для получения окончательного разворота. Если бы это было сделано в два этапа, это были бы два оператора, которые выглядят так же, как первые четыре оператора, но с разными шаблонами маски.

Я думаю, что после строки 4 шаблон будет 2,1,4,3,6,5,8,7, а не 4,3,2,1,8,7,6,5, как вы предполагали. Четыре части строки 5: 

8,7,0,0,0,0,0,0-->(i << 48)
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16)
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L)
0,0,0,0,0,0,2,1-->(i >>> 48)
1 голос
/ 02 марта 2012

Ваша попытка не совсем верна.Вот исправленная версия: 

2,1,4,3,6,5,8,7 --> i       //  Assume this sequence after line 4
8,7,0,0,0,0,0,0 --> (i << 48)
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16)
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L)
0,0,0,0,0,0,2,1 --> (i >>> 48)

Вот два разбитых средних шага: 

2,1,4,3,6,5,8,7 --> i       //  Assume this sequence after line 4
0,0,0,0,6,5,0,0 --> (i & 0xffff0000L)
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16)

2,1,4,3,6,5,8,7 --> i       //  Assume this sequence after line 4
0,0,2,1,4,3,6,5 --> (i >>> 16)
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L)

Хотя я немного удивлен, почему это не реализовано следующим образом:

i = (i & 0x5555555555555555L) <<  1 | (i >>>  1) & 0x5555555555555555L;  //  1
i = (i & 0x3333333333333333L) <<  2 | (i >>>  2) & 0x3333333333333333L;  //  2
i = (i & 0x0f0f0f0f0f0f0f0fL) <<  4 | (i >>>  4) & 0x0f0f0f0f0f0f0f0fL;  //  3
i = (i & 0x00ff00ff00ff00ffL) <<  8 | (i >>>  8) & 0x00ff00ff00ff00ffL;  //  4
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL;  //  5
i = (i & 0x00000000ffffffffL) << 32 | (i >>> 32) & 0x00000000ffffffffL;  //  6

Сохраняет последовательность шаблонов. И я думаю, что это также уменьшает количество операций.

РЕДАКТИРОВАТЬ: Я понимаю, почему он реализован таким, какой он есть.Версия в вопросе использует только 9 операций для двух последних разворотов.Версия здесь (строки 5 и 6) требует 10 операций .

Боже ... говорить о микрооптимизации до крайности ...

РЕДАКТИРОВАТЬ 2: Почему я не подумал об этом?Почему java.lang.Long не использует это? 

i = (i & 0x5555555555555555L) <<  1 | (i >>>  1) & 0x5555555555555555L;  //  1
i = (i & 0x3333333333333333L) <<  2 | (i >>>  2) & 0x3333333333333333L;  //  2
i = (i & 0x0f0f0f0f0f0f0f0fL) <<  4 | (i >>>  4) & 0x0f0f0f0f0f0f0f0fL;  //  3
i = (i & 0x00ff00ff00ff00ffL) <<  8 | (i >>>  8) & 0x00ff00ff00ff00ffL;  //  4
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL;  //  5
i = (i << 32) | (i >>> 32)                                               //  6
...