在64位整数内旋转(旋转90°)位矩阵(最多8x8位) [英] Rotating (by 90°) a bit matrix (up to 8x8 bits) within a 64-bit integer
问题描述
我有一个位矩阵(大小为6x6或7x7或8x8)存储在一个单个64位整数中.
I have a bit matrix (of size 6x6, or 7x7, or 8x8) stored within one single 64-bit integer.
我正在寻找将这些矩阵旋转90、180、270度的c ++代码，以及用于水平(垂直和垂直)移动和镜像这些矩阵的c ++代码.输出必须再次是64位整数.
I am looking for c++ code that rotates these matrices by 90, 180, 270 degrees, as well as c++ code for shifting (horizontally and vertically) and mirroring these matrices. The output must be again a 64-bit integer.
使用一些高级CPU指令集以及使用哈希表或类似技术可能没问题-速度是最重要的，并且RAM可用.我将在AMD Ryzen 7 1700八核PC上运行它.我不熟悉这些指令集(例如SSE2)，但是我在C ++中使用了__popcnt64()和_rotl64().
Using some of the advanced CPU instruction sets would probably be okay, as well as using hash tables or similar techniques - speed is of highest importance, and RAM is available. I will run this on an AMD Ryzen 7 1700 eight-core PC. I am not familiar with these instruction sets (e.g. SSE2), but I have used __popcnt64() and _rotl64() within C++.
有人能指出我正确的方向吗?我已经为7x7矩阵编写了自己的代码，但是现在我需要6x6和8x8的代码，想知道是否有人在此主题上发表过任何文章，也许比我的7x7方法更聪明.
Can anybody point me in the right direction? I have written my own code for the 7x7 matrix but I now need the code for 6x6 and 8x8 and wonder whether anybody has published anything on this topic, perhaps in a more clever way than my 7x7 approach.
顺便说一下，6x6和7x7矩阵分别存储在最低有效36位和49位中，其余位设置为零.
By the way, the 6x6 and 7x7 matrices are stored in the least significant 36 and 49 bits, respectively, with the remaining bits set to zero.
推荐答案
原则上，AVX2在这里非常有用.例如，要旋转90度，您可以执行以下操作:
In principle AVX2 can be quite useful here. For example, to rotate 90 degrees, you can do:
#include <stdio.h>
#include <immintrin.h>
#include <stdint.h>
/* gcc -O3 -Wall -m64 -mfma -mavx2 -march=skylake rot_bit_mat.c */
int print_bitmat(uint64_t k);
uint64_t bitmat_rot_90(uint64_t x){ /* 0xFEDCBA9876543210 */
__m256i mask1 = _mm256_set_epi64x(0x1010101010101010, 0x2020202020202020, 0x4040404040404040, 0x8080808080808080);
__m256i mask2 = _mm256_set_epi64x(0x0101010101010101, 0x0202020202020202, 0x0404040404040404, 0x0808080808080808);
__m256i x_bc = _mm256_set1_epi64x(x); /* Broadcast x */
__m256i r_lo = _mm256_and_si256(x_bc,mask1); /* Extract the right bits within bytes */
r_lo = _mm256_cmpeq_epi8(r_lo,mask1); /* Test if bits within bytes are set */
uint64_t t_lo = _mm256_movemask_epi8(r_lo); /* Move 32 bytes to 32 bit mask */
__m256i r_hi = _mm256_and_si256(x_bc,mask2);
r_hi = _mm256_cmpeq_epi8(r_hi,mask2);
uint64_t t_hi = _mm256_movemask_epi8(r_hi);
return t_lo | (t_hi << 32);
}
int main(int argc, char **argv){
/* 0xFEDCBA9876543210 */
uint64_t k = 0xA49B17E63298D5C3;
print_bitmat(k);
printf("\n");
print_bitmat(bitmat_rot_90(k));
printf("\n\n");
return 0;
}
int print_bitmat(uint64_t k){
uint64_t i,j;
for (i = 0; i < 8; i++){
for (j = 0; j < 8; j++){
printf("%llu",1ull & (k >> (i * 8ull + j)));
}
printf("\n");
}
return 0;
}
输出为:
$ ./a.out
11000011
10101011
00011001
01001100
01100111
11101000
11011001
00100101
11101011
11001000
00011001
01110110
00100010
01001101
10011110
11000110
类似的技术可能可以用于其他转换.尽管找出正确的位掩码可能需要一些时间.
It is likely that similar techniques can be used for other transformations. Although it may take some time to figure out the right bit masks.
对该问题的评论为其他转换提供了方向:
AVX2字节的位反转在此处引起关注，请参见此处
和此处.尽管后一个答案位相反
32位整数，而在您的情况下，需要将64位整数反转.因此，需要进行一些修改.
_bswap64()内部函数可用于倒置镜像位矩阵.
The comments on the question give directions for other transformations:
AVX2 bit reversal of bytes is of interest here, see here
and here. Although the latter answer bit reverses
32 bit ints, while in your case bit reversal of 64 bit ints is relevant; so, it needs some modifications.
The _bswap64() intrinsic can be used to mirror the bit matrix upside down.
这篇关于在64位整数内旋转(旋转90°)位矩阵(最多8x8位)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
