Пояснение относительно поворота растрового изображения на 90 °

Question

Недавно я нашел that SO question.

Принятый ответ и ответ, сделанный ревбаром, отлично работают, но я не понимаю, как они работают. И я не хочу использовать код, который я не понимаю в своем проекте. Я знаю, что такое битовые операции (shifts, ANDs, ORs и т. Д.), Но я не понимаю, как эти сборки операций заканчивают тем, что делают.

Благодарим вас за этот вопрос и, надеюсь, сможем мне помочь.

Answer 1

64-битное целое value представлено в виде 8-на-8 блок - давайте представим, что мы будем понимать «содержание» каждой ячейки следующим образом:

1 2 3 4 5 6 7 8 
9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64 

хотя value фактически сохраняются последовательно, как

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 

Мы также говорим, что сдвигая его влево на четыре (value << 4) приводит к

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 

или

5 6 7 8 9 10 11 12 
13 14 15 16 17 18 19 20 ... 

и сдвигая его вправо на четыре (value >> 4) дает

0 0 0 0 1 2 3 4 
    5 6 7 8 9 10 11 12 ... 

Теперь давайте

uint64 reflect_vert (uint64 value) 
{ 
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16); 
    value = ((value & 0xFF00FF00FF00FF00ull) >> 8) | ((value & 0x00FF00FF00FF00FFull) << 8); 
    return value; 
} 

Здесь 0xFFFFFFFF00000000ull -как куски бита маски, которые в сочетании с операцией И выбирают биты от value. Также обратите внимание, что 0xFF соответствует одному байту с восемью битами, поэтому 0xFFFFFFFF эффективно описывает 4*8=32 выбранных битов. Поскольку каждая строка имеет длину 8 бит, это соответствует 4 строкам.

В частности, value & 0xFFFFFFFF00000000ull выбирает (держит!) Верхние 32 бита value, то есть первые четыре строки, и отбрасывает остальные, в то время как value & 0x00000000FFFFFFFFull выбирает нижние 32 бита и отбрасывает первым.

Операция сдвиги в

((value & 0xFFFFFFFF00000000ull) >> 32) 
((value & 0x00000000FFFFFFFFull) << 32) 

затем переместить эти биты либо вниз (>> 32) на место нижних 32 бит или вверх (<< 32). Посредством OR-их вместе,

value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 

вы эффективно поменяли их.Теперь, так как нижний 32 бит соответствует «нижней части» блок, мы просто поменять местами строки, как так:

33 34 35 36 37 38 39 40 \ 
41 42 43 44 45 46 47 48 |__ 
49 50 51 52 53 54 55 56 | | 
57 58 59 60 61 62 63 64/| 
1 2 3 4 5 6 7 8 \ | 
9 10 11 12 13 14 15 16 |__| 
17 18 19 20 21 22 23 24 | 
25 26 27 28 29 30 31 32/

Performing же с 0xFFFF0000FFFF0000ull и 0x0000FFFF0000FFFFull, используя изменения шириной 16 свопов два ряда, каждые с соседи:

49 50 51 52 53 54 55 56 \__ 
57 58 59 60 61 62 63 64/| 
33 34 35 36 37 38 39 40 \__| 
41 42 43 44 45 46 47 48/
17 18 19 20 21 22 23 24 \__ 
25 26 27 28 29 30 31 32/| 
1 2 3 4 5 6 7 8 \__| 
9 10 11 12 13 14 15 16/

Наконец, 0xFF00FF00FF00FF00ull и 0x00FF00FF00FF00FFull со сдвигами 8 своп любой другой строки, в результате чего

57 58 59 60 61 62 63 64 _ 
49 50 51 52 53 54 55 56 
41 42 43 44 45 46 47 48 _ 
33 34 35 36 37 38 39 40 
25 26 27 28 29 30 31 32 _ 
17 18 19 20 21 22 23 24 
9 10 11 12 13 14 15 16 _ 
1 2 3 4 5 6 7 8 

, после чего блок успешно перевернулся вертикально.

Метод reflect_diag использует тот же подход для выборочных выборок. Дело в том, чтобы отметить здесь, что 0x0100000000000000 выбирает восемь-высокий (верхний ряд, слева от середины) бит:

0000 0001 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 

в то время как 0x0000000000000080 выбирает восемь наименьшую (нижний ряд, справа от середины)

0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 1000 0000 

бит. Они точно равны 49 бит, поэтому их смещение на 49 свопит их местоположение.

В другом примере шаблон 0x4020100804020100 выбирает биты

0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 
0000 0001 0000 0000 

, тогда как его коллега 0x0080402010080402 выбирает

0000 0000 1000 0000 
0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 

Вы заметите, что расстояния между битами образуют узор, который позволяет всю блок, который должен быть сдвинут таким образом, чтобы они совпадали с исходной позицией друг друга.

Также обратите внимание, что по сравнению с версиями с горизонтальным и вертикальным переворачиванием этот код не перезаписывает исходные значения, а представляет собой новый вывод. Код Мичиэля делает смещение на месте и кодирует сдвиги в восьмеричном, поэтому >> 010 фактически означает >> 8, 020 - 16 и так далее.