如何有效地转置2D位矩阵 [英] How to efficiently transpose a 2D bit matrix
本文介绍了如何有效地转置2D位矩阵的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我一直在解决这个问题（例如这个问题）。给定基本整数类型数组形式的2D位矩阵/板/阵列，例如，一个 long 的数组。为简单起见，我们可以假设一个方阵，例如，64位 long long 值的数组>。
让 x [i] 为 0< = i< 64 是输入数组。为 0< = i< = 64 计算一个数组 y [i] ，以便：
（x [i]>> j）& 1 ==（y [j]>> i）& 1
此处 x>>我是 x 的按位右移 i 位，& 是按位的，而 x [i] 是 i 数组中的位置 x 。
如何实现映射数组的函数 x 到数组 y 最有效率？
主要是我在寻找非破坏性的方法，保持输入数组 x 完整。
实施语言
使用的编程语言应该对整数类型进行数组和按位运算。许多语言都满足这些要求。 C / C ++和Java解决方案看起来非常相似，所以让我们选择这些语言。
解决方案
这似乎是问题的概括< a href =https://stackoverflow.com/questions/2243985/bitwise-transpose-of-8-bytes>按字节转置8个字节。这个问题只是大约8x8换位，所以你要问的是有点不同。但是你的问题也在 Hacker's Delight 一书的第7.3节中得到了解答（你可能能够看到 Google图书上的相关网页。在那里呈现的代码显然源于 Guy Steele 。
Hacker's Delight网站仅包含本书中的源代码。 8x8 和 32x32 案例，但后者琐碎地概括为您的64x64案例：
#include< stdint.h>
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））&米;
a [k] ^ = t;
a [k | j] ^ =（t << j）;
}
}
}
这种方式的工作方式是该函数连续交换较小的位块，从32x32块开始（不在那些块中转换位），之后在那些32x32块内交换相应的16x16块等等。持有的变量块大小为 j 。因此，外循环 j 连续取值32,16,8,4,2和1，这意味着外循环运行六次。内部循环遍历 half 您的位行，即变量 k 中给定位的行等于零。当 j 为32时，这些是0-31行，当 j 为16时，这些是0-15行和32-47等。环的内部一起运行6 * 32 = 192次。在这个内部部件中发生的是掩码 m 确定应该交换的位数，在 t 中xor或那些位被计算，并且xor-ed位列表用于适当地更新两个位中的位。
书（和网站）也有这个代码的一个版本，其中这些循环都已展开，并且掩码 m 未计算，但只是已分配。我想这取决于寄存器的数量和指令缓存的大小是否有所改善？
为了测试这是否有效，假设我们定义了一些模式，说：
uint64_t logo [] = {
0b0000000000000000000000000000000000000000000100000000000000000000，
0b0000000000000000000000000000000000000000011100000000000000000000，
0b0000000000000000000000000000000000000000111110000000000000000000，
0b0000000000000000000000000000000000000001111111000000000000000000，
0b0000000000000000000000000000000000000000111111100000000000000000，
0b0000000000000000000000000000000000000000111111100000000000000000，
0b0000000000000000000000000000000000000000011111110000000000000000，
0b0000000000000000000000000000000000000000001111111000000000000000，
0b0000000000000000000000000000000000000000001111111100000000000000，
0b0000000000000000000000000000000010000000000111111100000000000000，
0b000 0000000000000000000000000000011100000000011111110000000000000，
0b0000000000000000000000000000000111110000000001111111000000000000，
0b0000000000000000000000000000001111111000000001111111100000000000，
0b0000000000000000000000000000011111111100000000111111100000000000，
0b0000000000000000000000000000001111111110000000011111110000000000，
0b0000000000000000000000000000000011111111100000001111111000000000，
0b0000000000000000000000000000000001111111110000001111111100000000，
0b0000000000000000000000000000000000111111111000000111111100000000，
0b0000000000000000000000000000000000011111111100000011111110000000，
0b0000000000000000000000000000000000001111111110000001111111000000，
0b0000000000000000000000000000000000000011111111100001111111100000，
0b0000000000000000000000001100000000000001111111110000111111100000，
0b0000000000000000000000001111000000000000111111111000011111110000，
0b000000000000000000000001111111000000000001111111110000 1111100000，
0b0000000000000000000000011111111100000000001111111110001111000000，
0b0000000000000000000000111111111111000000000011111111100110000000，
0b0000000000000000000000011111111111110000000001111111110000000000，
0b0000000000000000000000000111111111111100000000111111111000000000，
0b0000000000000000000000000001111111111111100000011111110000000000，
0b0000000000000000000000000000011111111111111000001111100000000000，
0b0000000000000000000000000000000111111111111110000011000000000000，
0b0000000000000000000000000000000001111111111111100000000000000000，
0b0000000000000000000000000000000000001111111111111000000000000000，
0b0000000000000000000000000000000000000011111111111100000000000000，
0b0000000000000000000111000000000000000000111111111100000000000000，
0b0000000000000000000111111110000000000000001111111000000000000000，
0b0000000000000000000111111111111100000000000011111000000000000000，
0b00000000000000000001111111111111 11110000000000110000000000000000，
0b0000000000000000001111111111111111111111100000000000000000000000，
0b0000000000000000001111111111111111111111111111000000000000000000，
0b0000000000000000000000011111111111111111111111100000000000000000，
0b0000001111110000000000000001111111111111111111100000111111000000，
0b0000001111110000000000000000000011111111111111100000111111000000，
0b0000001111110000000000000000000000000111111111100000111111000000，
0b0000001111110000000000000000000000000000001111000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000001111111111111111111111111111000000111111000000，
0b0000001111110000001111111111111111111111111111000000111111000000，
0b0000001111110000001111111111111111111111111111000000111111000000，
0b0000001111110000001111111111111111111111111111000000111111000000，
0b0000001111 110000001111111111111111111111111111000000111111000000，
0b0000001111110000001111111111111111111111111111000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111110000000000000000000000000000000000000000111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
0b0000001111111111111111111111111111111111111111111111111111000000，
};
然后我们调用 transpose32 函数并打印结果位模式：
#include< stdio.h>
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）;
返回0;
}
然后这将作为输出：
'pre>
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000011111111111111111111111
0000000000000000000000000000000000000000000000000000000000111 111
0000000000000000000000000000000000000000000000000000000000111111
0000000000000000000000000000000000000000000000000000000000111111
0000000000000000000000000000000000000000000000000000000000111111
0000000000000000000000000000000000000000000000000000000000111111
0000000000000000000000000000000000000000000000000000000000111111
0000000000000000000000000000000000000011000000011111100000111111
0000000000000000000000000000000000111111000000011111100000111111
0000000000000000000000000000000000111111000000011111100000111111
0000000000000000000000000000000000111111000000011111100000111111
0000000000000000000000000100000000011111000000011111100000111111
0000000000000000000000011110000000011111100000011111100000111111
0000000000000000000001111110000000011111100000011111100000111111
000000000000000000000111111100001111110000000011111100000111111
0000000000000000000000111111000000011111100000011111100000111111
00000000000 00000000000111111100000001111110000011111100000111111
0000000000000000000000011111100000001111110000011111100000111111
0000000000000100000000011111110000001111110000011111100000111111
0000000000001110000000001111110000001111110000011111100000111111
0000000000011110000000001111111000001111110000011111100000111111
0000000001111111000000000111111000000111111000011111100000111111
0000000000111111100000000111111100000111111000011111100000111111
0000000000111111110000000011111100000111111000011111100000111111
0000000000011111111000000011111100000111111000011111100000111111
0000000000001111111100000001111110000011111000011111100000111111
0000000000000111111100000001111110000011111100011111100000111111
0000000000000011111110000000111111000011111100011111100000111111
0001000000000001111111000000111111000011111100011111100000111111
0011110000000001111111100000111111100011111100011111100000111111
0111111000000000111111110000011 111100001111100011111100000111111
0111111110000000011111111000011111110001111110011111100000111111
1111111111000000001111111000001111110001111110011111100000111111
0011111111100000000111111100001111111001111110011111100000111111
0001111111111000000011111110000111111001111110011111100000111111
0000111111111100000011111111000111111100111100000000000000111111
0000001111111110000001111111100011111100000000000000000000111111
0000000111111111100000111111110011111000000000000000000000111111
0000000011111111110000011111110001100000000000000000000000111111
0000000000111111111000001111111000000000000000000000000000111111
0000000000011111111110000111111000000000000000000000000000111111
0000000000001111111111000111110000000000011111111111111111111111
0000000000000011111111100011100000000000011111111111111111111111
0000000000000001111111111001000000000000011111111111111111111111
000000000000000011111111110000000000000001111111111 1111111111111
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））&米;
y [k] ^ = t;
y [k | j] ^ =（t << j）;
}
}
}
与其他版本的无论架构的字节顺序如何，这都不会 工作。此外，我知道C标准不允许您以 uint32_t 的数组访问 uint64_t 的数组。但是，我喜欢它，当你这样做时，移动块周围循环的第一次迭代不需要移位或xors。
I keep stumbling over this problem (e.g. in this question). Given a 2D bit matrix/board/array in the form of an array of primitive integer types, e.g. an array of long. For simplicity, we can assume a square matrix, e.g., an array of 64 long values on platforms that have 64 bit long.
Let x[i] for 0 <= i < 64 be the input array. Compute an array y[i] for 0 <= i <= 64 such that:
(x[i] >> j) & 1 == (y[j] >> i) & 1
Here x >> i is the bitwise right-shift of x by i bits, & is bitwise and, and x[i] is the value at ith position in array x.
How to implement a function that maps array x to array y most efficiently?
Primarily I am looking for non-destructive methods, which leave the input array x intact.
Implementation language
The used programming language should have arrays and bitwise operations on integer types. Many languages fulfill these requirements. C/C++ and Java solutions will look very similar, so let's choose these languages.
解决方案
This seems a generalization of the question Bitwise transpose of 8 bytes. That question was just about 8x8 transposition, so what you are asking is a bit different. But your question is answered just as well in section 7.3 of the book Hacker's Delight (you might be able to see the relevant pages on Google books). The code that is presented there apparently originates with Guy Steele.
The Hacker's Delight website only contains the source code from the book for the 8x8 and 32x32 cases, but the latter generalizes trivially to your 64x64 case:
#include <stdint.h>
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);
}
}
}
The way that this works is that the function swaps successively smaller blocks of bits, starting with 32x32 blocks (without transposing the bit within those blocks), after that within those 32x32 blocks it swaps the appropriate 16x16 blocks, etc. The variable that holds the block size is j. Therefore, the outer loop has j succcessively take the values 32, 16, 8, 4, 2 and 1, which means that the outer loop runs six times. The inner loop runs over half the lines of your of bits, the lines where a given bit in the variable k is equal to zero. When j is 32 those are the lines 0-31, when j is 16 those are the lines 0-15 and 32-47, etc. Together the inner part of the loop runs 6*32 = 192 times. What happens inside this inner part is that the mask m determines what are the bits that should be swapped, in t the xor or those bits are calculated, and that xor-ed lists of bits is used to update the bits in both places appropriately.
The book (and the website) also has a version of this code in which these loops have both been unrolled, and where the mask m is not calculated, but just assigned. I guess it depends on things like the number of registers and the size of your instruction cache whether that is an improvement?
To test that this works, suppose we define some bit pattern, say:
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,
};
We then call the transpose32 function and print the resulting bit pattern:
#include <stdio.h>
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;
}
And this then gives as output:
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
Which is nicely flipped, as we hoped for.
Edit:
This is actually not really what you asked for, as you asked for a non-destructive version of this code. You can get this by having the first swap of the 32x32 blocks go from x to y. For instance, you might do something like:
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);
}
}
}
Unlike the other version of the code this does not work regardless of endianness of the architecture. Also, I know that the C standard does not allow you to access an array of uint64_t as an array of uint32_t. However, I like it that no shifts or xors are needed for the first iteration of the move-the-blocks-around loop when you do it like this.
这篇关于如何有效地转置2D位矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
