字节内的比特交换之蝶式算法#

在串行发送数据时，可能是左移，也有可能是右移；在接收端，可能要求最高位在前，也有可能是最低位在前。发送与接收的顺序得一致。如果不一致，可以考虑：

改变发送端的左/右移的方向，或者
修改移出前的数据

蝶式算法交换比特#

如果要发送的数据是 1,2,3,4,5,6,7,8。

如果发送顺序只能是 MSB 先发，可是接收希望方希望接收的顺序是 8,7,8,5,4,3,2,1。

此时不防考虑在发送前，先得到数据 8,7,6,5,4,3,2,1

蝶式算法的交换比特就是为了解决这个问题的。

算法描述

byte byte_flip(byte data) {
  data = (data << 4) | (data >> 4);   // step 1
  data = ((data << 2) & 0xcc) | ((data >> 2) & 0x33);  // step 2
  data = ((data << 1) & 0xaa) | ((data >> 1) & 0x55);  // step 3
  return data;
}

说明： byte_flip() 操作的对象是字节内的比特。但为了方便阅读，我们将每个位的值写成 1~8 之间的数，而不仅仅是1 或0.

验证

在 byte_flip 前，数据是 1,2,3,4,5,6,7,8, 验证 byte_flip 后的顺序为 8,7,6,5,4,3,2,1

step 1

5,6,7,8,1,2,3,4

step 2

7,8,1,2,3,4,0,0 | 0,0,5,6,7,8,1,2

1,1,0,0,1,1,0,0 | 0,0,1,1,0,0,1,1

7,8,0,0,3,4,0,0 |0,0,5,6,0,0,3,2

7,8,5,6,3,4,1,2

step 3

8,5,6,3,4,1,2,0 | 0,7,8,5,6,3,4,1

1,0,1,0,1,0,1,0 | 0,1,0,1,0,1,0,1

8,0,6,0,4,0,2,0 | 0,7,0,5,0,3,0,1

8,7,6,5,4,3,2,1