c++ - 关于将位图旋转 90° 的说明

Question

我最近找到了that SO question .

接受的答案和大黄做出的答案都很好，但我不明白它们是如何工作的。而且我不想在我的项目中使用我不理解的代码。我知道基本的位操作是什么(移位、AND、OR 等)，但我不明白这些操作组合最终如何完成它们正在做的事情。

感谢您查看这个问题，希望能对我有所帮助。

Answer 1

64 位整数 value表示为一个 8×8 block - 让我们假设我们理解每个单元格的“内容”如下:

 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 -like 片段是位掩码，结合 AND 操作，从 value 中选择位.另请注意 0xFF对应于设置了八位的一个字节，所以 0xFFFFFFFF有效地描述了 4*8=32选定的位。由于每一行都是 8位长，这对应于 4行。

具体来说，value & 0xFFFFFFFF00000000ull选择(保留!)value 的高 32 位，即前四行，并丢弃其余的，而 value & 0x00000000FFFFFFFFull选择低 32 位并丢弃第一个。 (它实际上并没有丢弃任何东西，而是将那些不匹配的元素/位置的值设置为零。)

类次操作

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

然后将这些位向下移动 (>> 32) 到低 32 位的位置或向上移动 (<< 32)。通过将它们组合在一起，

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

你已经有效地交换了它们。现在由于低 32 位对应于 block 的“下半部分”，我们只是像这样交换行:

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 /

对 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

此时方 block 已成功垂直翻转。

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

您会注意到，位之间的距离形成一种模式，允许整个 block 移动，使它们与彼此的原始位置对齐。

另请注意，与水平和垂直翻转版本相比，此代码不会覆盖原始值，而是组成一个新的输出。 Michiel 的代码就地进行移位并以八进制编码移位，因此 >> 010实际上意味着 >> 8 , 020是16等等。