如何有效地转置2D位矩阵
我一直在绊倒这个问题（例如在这个问题中 ）。 给定基本整数类型数组forms的2D位矩阵/板/arrays，例如long数组。 为简单起见，我们可以假设一个方阵，例如，在64位long平台上具有64个long值的数组。
令x[i]为0 <= i < 64为输入数组。 计算数组y[i]为0 <= i <= 64这样：
(x[i] >> j) & 1 == (y[j] >> i) & 1
这里x >> i是x >> i的按位右移i位， &是按位，并且x[i]是数组x第i个位置的值。
如何实现一个最有效地将数组x映射到数组y的函数？
主要是我正在寻找非破坏性的方法，使输入数组x完好无损。
实施语言
使用的编程语言应该对整数类型进行数组和按位运算。 许多语言都满足这些要求。 C / C ++和Java解决方案看起来非常相似，所以让我们选择这些语言。
这似乎是对8字节的Bitwise转置问题的推广。 这个问题只是大约8×8换位，所以你要问的是有点不同。 但是你的问题在Hacker’s Delight一书的第7.3节中得到了回答（你可能会在Google书籍上看到相关的页面 ）。 在那里展示的代码显然源于Guy Steele 。
Hacker’s Delight网站仅包含本书中针对8×8和32×32案例的源代码，但后者简单地概括为64×64案例：
#include void transpose64(uint64_t a[64]) { int j, k; uint64_t m, t; for (j = 32, m = 0x00000000FFFFFFFF; j; j >>= 1, m ^= m << j) { for (k = 0; k < 64; k = ((k | j) + 1) & ~j) { t = (a[k] ^ (a[k | j] >> j)) & m; a[k] ^= t; a[k | j] ^= (t << j); } } }
这种方法的工作方式是该函数连续交换较小的位块，从32x32块开始（不在这些块内转置位），然后在那些32x32块内交换相应的16x16块，等等。块大小是j 。 因此，外环有j连续取值32,16,8,4,2和1，这意味着外环运行六次。 内部循环遍历位的一半行，即变量k中给定位等于零的行。 当j是32时，那些是0-31行，当j是16时，那些是0-15和32-47等等。循环的内部一起运行6 * 32 = 192次。 在这个内部部分内部发生的是掩码m确定应该交换的比特，在xor或那些比特的计算中，并且xor-ed比特列表用于适当地更新两个比特中的比特。
本书（和网站）也有这个代码的一个版本，其中这些循环都已展开，并且掩码m未计算，但只是分配。 我想这取决于寄存器的数量和指令缓存的大小是否有所改善？
为了测试这是否有效，假设我们定义了一些位模式，比如：
uint64_t logo[] = { 0b0000000000000000000000000000000000000000000100000000000000000000, 0b0000000000000000000000000000000000000000011100000000000000000000, 0b0000000000000000000000000000000000000000111110000000000000000000, 0b0000000000000000000000000000000000000001111111000000000000000000, 0b0000000000000000000000000000000000000000111111100000000000000000, 0b0000000000000000000000000000000000000000111111100000000000000000, 0b0000000000000000000000000000000000000000011111110000000000000000, 0b0000000000000000000000000000000000000000001111111000000000000000, 0b0000000000000000000000000000000000000000001111111100000000000000, 0b0000000000000000000000000000000010000000000111111100000000000000, 0b0000000000000000000000000000000011100000000011111110000000000000, 0b0000000000000000000000000000000111110000000001111111000000000000, 0b0000000000000000000000000000001111111000000001111111100000000000, 0b0000000000000000000000000000011111111100000000111111100000000000, 0b0000000000000000000000000000001111111110000000011111110000000000, 0b0000000000000000000000000000000011111111100000001111111000000000, 0b0000000000000000000000000000000001111111110000001111111100000000, 0b0000000000000000000000000000000000111111111000000111111100000000, 0b0000000000000000000000000000000000011111111100000011111110000000, 0b0000000000000000000000000000000000001111111110000001111111000000, 0b0000000000000000000000000000000000000011111111100001111111100000, 0b0000000000000000000000001100000000000001111111110000111111100000, 0b0000000000000000000000001111000000000000111111111000011111110000, 0b0000000000000000000000011111110000000000011111111100001111100000, 0b0000000000000000000000011111111100000000001111111110001111000000, 0b0000000000000000000000111111111111000000000011111111100110000000, 0b0000000000000000000000011111111111110000000001111111110000000000, 0b0000000000000000000000000111111111111100000000111111111000000000, 0b0000000000000000000000000001111111111111100000011111110000000000, 0b0000000000000000000000000000011111111111111000001111100000000000, 0b0000000000000000000000000000000111111111111110000011000000000000, 0b0000000000000000000000000000000001111111111111100000000000000000, 0b0000000000000000000000000000000000001111111111111000000000000000, 0b0000000000000000000000000000000000000011111111111100000000000000, 0b0000000000000000000111000000000000000000111111111100000000000000, 0b0000000000000000000111111110000000000000001111111000000000000000, 0b0000000000000000000111111111111100000000000011111000000000000000, 0b0000000000000000000111111111111111110000000000110000000000000000, 0b0000000000000000001111111111111111111111100000000000000000000000, 0b0000000000000000001111111111111111111111111111000000000000000000, 0b0000000000000000000000011111111111111111111111100000000000000000, 0b0000001111110000000000000001111111111111111111100000111111000000, 0b0000001111110000000000000000000011111111111111100000111111000000, 0b0000001111110000000000000000000000000111111111100000111111000000, 0b0000001111110000000000000000000000000000001111000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000001111111111111111111111111111000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111110000000000000000000000000000000000000000111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, 0b0000001111111111111111111111111111111111111111111111111111000000, };
然后我们调用transpose32函数并打印生成的位模式：
#include void printbits(uint64_t a[64]) { int i, j; for (i = 0; i < 64; i++) { for (j = 63; j >= 0; j--) printf("%c", (a[i] >> j) & 1 ? '1' : '0'); printf("\n"); } } int main() { transpose64(logo); printbits(logo); return 0; }
然后这给出了输出：
0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000011111111111111111111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000000000000000000000000111111 0000000000000000000000000000000000000011000000011111100000111111 0000000000000000000000000000000000111111000000011111100000111111 0000000000000000000000000000000000111111000000011111100000111111 0000000000000000000000000000000000111111000000011111100000111111 0000000000000000000000000100000000011111000000011111100000111111 0000000000000000000000011110000000011111100000011111100000111111 0000000000000000000001111110000000011111100000011111100000111111 0000000000000000000001111111000000011111100000011111100000111111 0000000000000000000000111111000000011111100000011111100000111111 0000000000000000000000111111100000001111110000011111100000111111 0000000000000000000000011111100000001111110000011111100000111111 0000000000000100000000011111110000001111110000011111100000111111 0000000000001110000000001111110000001111110000011111100000111111 0000000000011110000000001111111000001111110000011111100000111111 0000000001111111000000000111111000000111111000011111100000111111 0000000000111111100000000111111100000111111000011111100000111111 0000000000111111110000000011111100000111111000011111100000111111 0000000000011111111000000011111100000111111000011111100000111111 0000000000001111111100000001111110000011111000011111100000111111 0000000000000111111100000001111110000011111100011111100000111111 0000000000000011111110000000111111000011111100011111100000111111 0001000000000001111111000000111111000011111100011111100000111111 0011110000000001111111100000111111100011111100011111100000111111 0111111000000000111111110000011111100001111100011111100000111111 0111111110000000011111111000011111110001111110011111100000111111 1111111111000000001111111000001111110001111110011111100000111111 0011111111100000000111111100001111111001111110011111100000111111 0001111111111000000011111110000111111001111110011111100000111111 0000111111111100000011111111000111111100111100000000000000111111 0000001111111110000001111111100011111100000000000000000000111111 0000000111111111100000111111110011111000000000000000000000111111 0000000011111111110000011111110001100000000000000000000000111111 0000000000111111111000001111111000000000000000000000000000111111 0000000000011111111110000111111000000000000000000000000000111111 0000000000001111111111000111110000000000011111111111111111111111 0000000000000011111111100011100000000000011111111111111111111111 0000000000000001111111111001000000000000011111111111111111111111 0000000000000000111111111100000000000000011111111111111111111111 0000000000000000001111111100000000000000011111111111111111111111 0000000000000000000111111000000000000000011111111111111111111111 0000000000000000000011110000000000000000000000000000000000000000 0000000000000000000000100000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000
正如我们所希望的那样，这很好地翻转了。
编辑：
这实际上并不是你要求的，因为你要求这个代码的非破坏性版本。 您可以通过将32x32块的第一次交换从x转到y 。 例如，您可能会执行以下操作：
void non_destructive_transpose64(uint64_t x[64], uint64_t y[64]) { int j, k; uint64_t m, t; for (k = 0; k < 64; k += 2) { ((uint32_t *) y)[k] = ((uint32_t *) x)[k ^ 64 + 1]; ((uint32_t *) y)[k + 1] = ((uint32_t *) x)[k + 1]; } for (; k < 128; k += 2) { ((uint32_t *) y)[k] = ((uint32_t *) x)[k]; ((uint32_t *) y)[k + 1] = ((uint32_t *) x)[k ^ 64]; } for (j = 16, m = 0x0000FFFF0000FFFF; j; j >>= 1, m ^= m << j) { for (k = 0; k < 64; k = ((k | j) + 1) & ~j) { t = (y[k] ^ (y[k | j] >> j)) & m; y[k] ^= t; y[k | j] ^= (t << j); } } }
与其他版本的代码不同，无论架构的字节顺序如何，这都不起作用。 此外，我知道C标准不允许您作为uint32_t数组访问uint64_t数组。 但是，我喜欢它，当你这样做时，移动块周围循环的第一次迭代不需要移位或xors。