在64位整数中旋转一个最大为8x8位的位矩阵（顺时针旋转90度）。

Question

在64位整数中旋转一个最大为8x8位的位矩阵（顺时针旋转90度）。

c++bit-manipulationx86-64avxmicro-optimization

3

我有一个大小为6x6、7x7或8x8的位矩阵，存储在一个64位整数中。我正在寻找C++代码，以将这些矩阵旋转90度、180度、270度，以及移动(水平和垂直)和镜像这些矩阵。输出必须再次是一个64位整数。可以使用一些高级CPU指令集，也可以使用哈希表或类似技术-速度最重要，RAM可用。我将在一个AMD Ryzen 7 1700八核PC上运行此代码。我不熟悉这些指令集(SSE2等)，但我已经在C++中使用了__popcnt64()和_rotl64()。请问有谁能指点我正确的方向？我已经为7x7矩阵编写了自己的代码，但现在我需要6x6和8x8的代码，并想知道是否有人在这个主题上发表过任何东西，可能比我的7x7方法更聪明。顺便说一下，6x6和7x7矩阵分别存储在最低有效36位和49位中，其余位设置为零。

- fmb

2

这可能会被关闭，因为它是一个关于库或类似内容的请求。请查看 [ask]。只需问什么是最好的方法。如果您只想找到已经存在的实现，则可以在Google上提出问题。如果您想了解实际上最好/最有效的实现方式，则应该在Stack Overflow上提问。 - Peter Cordes

4

已经有很多关于8x8旋转的问题了，包括“如何在8x8位块上最快地旋转位?”,“如何高效地转置2D比特矩阵?”,“翻转字节数组的位-性能改进”。现在您需要实现6x6的旋转。 - phuclv

2

要将6x6矩阵或其次对角线周围的行向左旋转90°，请使用mat*0x810204081 & 0x820820820，就像我在8x8中使用的那样。 - phuclv

2

你有没有考虑将7x7位存储为0, 0, ..., 0, 0, b48, ...b42,...,0, b20, ...,b14, 0, b13, ..., b7, 0, b6, ... , b0，即在中间填充7个1个零位，并在末尾额外添加8个零位。这样，您可以在7x7情况下重复使用所有现有的互联网上的8x8代码。您只需要在最后进行一次额外的位移，以获取正确位置的位。 - wim

1

@wim：我也是这么想的。对于6x6和7x7，最好将其解包为8位行跨度，以便进行SIMD字节操作。例如，对于180度旋转或镜像，可以使用_mm_shuffle_epi8，对于每个字节内的位反转（使用4位查找表）+右移1或2。标量bswap + shift可以进行字节反转，因此您可能需要将shift组合在一起。在没有pext / pdep的情况下解包到该格式很糟糕。https://godbolt.org/z/6cUhIL设计注释用于标量and / andn（BMI1）+ ADD或LEA。（使用x+x = x<<1掩码移动一些位，但是x+ (x&mask)。 - Peter Cordes

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wim · Accepted Answer

原则上，AVX2在这里可以非常有用。例如，要旋转90度，可以执行以下操作：

#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;
}

输出结果为：

很可能类似的技术可以用于其他转换。虽然找到正确的位掩码可能需要一些时间。

问题评论提供了其他转换的指导： AVX2字节位反转在这里很有意义，请参见此处和此处。尽管后一个答案位反转32位整数，而在您的情况下，位反转64位整数是相关的，因此需要进行一些修改。 _bswap64()内置函数可以用于上下翻转位矩阵。