什么是最快的方式来旋转位的8x8块中的位？ [英] What is the fastest way to rotate the bits in an 8x8 block on bits?

问题描述

我不知道我正在努力做什么的确切术语。我有一个 8x8 块位存储在 8个字节 ，每个字节存储一行。完成后，我想让每个字节存储一列。

例如，完成后：

  Byte0out = Byte0inBit0 + Byte1inBit0 + Byte2inBit0 + Byte3inBit0 + ... 
 Byte1out = Byte0inBit1 + Byte1inBit1 + Byte2inBit1 + Byte3inBit1 + ... 
  

在 C 中执行此操作的最简单的方法是什么？

解决方案

此代码直接从Hacker's Delight - 图7-2将8x8-位矩阵，我没有信用：

  void transpose8（unsigned char A [8]，int m ，int n，
 unsigned char B [8]）{
 unsigned x，y，t; 
 
 //加载数组并将其打包成x和y。 
 
 x =（A [0]<< 24）| （A [m] <16）| （A [2 * m] <8）| A [3 * M]; 
 y =（A [4 * m] << 24）| （A [5 * m] <16）| （A [6 * m] <8）| A [7 *米]。 
 
 t =（x ^（x>> 7））& 0x00AA00AA; x = x ^ t ^（t << 7）; 
 t =（y ^（y>>> 7））& 0x00AA00AA; y = y ^ t ^（t << 7）; 
 
 t =（x ^（x>>> 14））& 0x0000CCCC; x = x ^ t ^（t <14）; 
 t =（y ^（y>>>> 14））& 0x0000CCCC; y = y ^ t ^（t <14）; 
 
 t =（x& 0xF0F0F0F0）| （（y> 4）& 0x0F0F0F0F）; 
 y =（（x< 4）& 0xF0F0F0F0）| （y& 0x0F0F0F0F）; 
 x = t; 
 
 B [0] = x>> 24; B [n]的= X>> 16; B [2 * N] = X>> 8; B [3 * N] = X; 
 B [4 * n] = y>> 24; B [5 * N] = Y>> 16; B [6 * N] = Y>> 8; B [7 * N] = Y; 
} 
  

我没有检查是否按照您需要的方向旋转，如果不是您可能需要调整代码。

另外，请记住数据类型和大小 - int &

BTW，我怀疑这本书（Hacker's Delight ）对于你正在做的那种工作来说是至关重要的 - 检查出来，那里有很多好东西。

I'm not sure the exact term for what I'm trying to do. I have an 8x8 block of bits stored in 8 bytes, each byte stores one row. When I'm finished, I'd like each byte to store one column.

For example, when I'm finished:

Byte0out = Byte0inBit0 + Byte1inBit0 + Byte2inBit0 + Byte3inBit0 + ...
Byte1out = Byte0inBit1 + Byte1inBit1 + Byte2inBit1 + Byte3inBit1 + ...

What is the easiest way to do this in C which performs well?

解决方案

This code is cribbed directly from "Hacker's Delight" - Figure 7-2 Transposing an 8x8-bit matrix, I take no credit for it:

void transpose8(unsigned char A[8], int m, int n, 
                unsigned char B[8]) {
   unsigned x, y, t; 

   // Load the array and pack it into x and y. 

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m]; 
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m]; 

   t = (x ^ (x >> 7)) & 0x00AA00AA;  x = x ^ t ^ (t << 7); 
   t = (y ^ (y >> 7)) & 0x00AA00AA;  y = y ^ t ^ (t << 7); 

   t = (x ^ (x >>14)) & 0x0000CCCC;  x = x ^ t ^ (t <<14); 
   t = (y ^ (y >>14)) & 0x0000CCCC;  y = y ^ t ^ (t <<14); 

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F); 
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F); 
   x = t; 

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x; 
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y; 
}

I didn't check if this rotates in the direction you need, if not you might need to adjust the code.

Also, keep in mind datatypes & sizes - int & unsigned (int) might not be 32 bits on your platform.

BTW, I suspect the book (Hacker's Delight) is essential for the kind of work you're doing... check it out, lots of great stuff in there.

这篇关于什么是最快的方式来旋转位的8x8块中的位？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！