【算法】蝶式交换，字节高低位交换

晓宇芯片之家 2021-01-31

蝶式交换

今天在控制板上对一个协议进行具体的实现，协议要求字节低位在左，高位在右，与常规的数据格式不一样，原文要求是这样的：

所以，在发送之前，必须对每个字节做转换处理，逐个交换其高低位，例如11010001，经过0-7，1-6，2-5，3-4对应位的交换，变成10001011 。

开始的解决思路是这样的：

unsigned char shift_fun1(unsigned char data)  
{  
    unsigned char i;  
    unsigned char tmp=0x00;  
    for(i=0;i<8;i++)  
    {  
        tmp=((data>>i)&0x01)|tmp;  
        if(i<7)  
            tmp=tmp<<1;  
    }  
    printf("  after shift fun1 data=%x \n",tmp);  
    return tmp;    
}

温馨提示：代码可左右滑动

上述代码实现起来不难，而且效率还是比较高的。但是还有比这更简洁的解决方法，在嵌入式开发中遇到交换字节位的问题时通常使用蝶式交换法和查表法来实现。查表法顾名思义即将一些值存到内存中，需要计算时查表即可，但是也会占用额外的存储空间。这里主要再介绍一下蝶式交换法。

所谓的蝶式交换是这样的：

data=(data<<4)|(data>>4);  
data=((data<<2)&0xcc)|((data>>2)&0x33);  
data=((data<<1)&0xaa)|((data>>1)&0x55);

我们可以做一下执行演算：

假设原始位序列为 0 1 0 1 1 0 0 1

data=(data<<4)|(data>>4);之后序列为 1 0 0 1 0 1 0 1

data=((data<<2)&0xcc)|((data>>2)&0x33); 之后序列为 0 1 1 0 0 1 0 1

data=((data<<1)&0xaa)|((data>>1)&0x55); 之后序列为 1 0 0 1 1 0 1 0

更抽象的来说原始位为 1 2 3 4 5 6 7 8

data=(data<<4)|(data>>4); 之后位序为 5 6 7 8 1 2 3 4

data=((data<<2)&0xcc)|((data>>2)&0x33); 之后位序为 7 8 5 6 3 4 1 2

data=((data<<1)&0xaa)|((data>>1)&0x55); 之后位序为 8 7 6 5 4 3 2 1

由此完成了整个位的逆序转换，下面是具体的实现代码：

unsigned char shift_fun2(unsigned char data)  
{  
    data=(data<<4)|(data>>4);  
    data=((data<<2)&0xcc)|((data>>2)&0x33);  
    data=((data<<1)&0xaa)|((data>>1)&0x55);  
    printf("  after shift fun2 data=%x \n",data);  
  
    return data;  
}