当前位置: 首页 > >

位逆序(位反转)问题

发布时间:

位逆序或位反转,就是 把一串bit序列按相反的方向排列。


有很多方法,首先最简单的,一个一个位取出来重新排列:



typedefunsignedchar?MYWORD;
#define BITS_OF_LEN??????? 8

MYWORD ReverseBits1(MYWORD?num)
{
??? MYWORD ret=0;
??? int i;

??? for(i=0;i??? {
??????? ret <<=1;
??????? ret |=num&1;
??????? num >>=1;
??? }
??? return ret;
}


一次一个bit,源串右移,目标串左移,实现了位反转。


还可以直接把bit移动到需要的位置:



MYWORD?ReverseBits2(MYWORD?num)
{
??? MYWORD ret=0;
??? int i;

??? for(i=0;i< (BITS_OF_LEN/2);i++)
??? {
???????? ret |= ((num& (1<???????? ret |= ((num& (1<< (BITS_OF_LEN-1-i)))>> (BITS_OF_LEN-2*i-1));
??? }
??? return ret;
}


后半部分前移,前半部分后移。


上面两种方法可以用于任意个数的bit序列,如果是特定的位数,如一个字节8位,可以用如下代码,效率高一些:



MYWORD?ReverseBits3(MYWORD?num)
{
??? num = ((num&0x0f)<<4) | ((num&0xf0)>>4);
??? num = ((num&0x33)<<2) | ((num&0xcc)>>2);
??? num = ((num&0x55)<<1) | ((num&0xaa)>>1);
??? return num;
}


原理吗,如下:


12345678


56781234


78563412


87654321


逐步分块解决,这三句顺序可以倒过来,效果一样。


写成下面这样更好看,效率一样:



MYWORD?ReverseBits4(MYWORD?num)
{
??? num = ((num&0x0f)<<4) | ((num>>4)&0x0f);
??? num = ((num&0x33)<<2) | ((num>>2)&0x33);
??? num = ((num&0x55)<<1) | ((num>>1)&0x55);
??? return num;
}


还可以用位域来实现,不过移植性差,效率也不高。


效率最高的还是查表了,如8位只需要256个字节的数组。


MYWORD rbits[]={?0,128,64,192,...127,255};


x位反转后的值就是rbits[x],效率自然高了。


从PC上的测试看,如果查表用的时间为1的话,第一种方法为11,第二种为7,第三种第四种为5.要用位域实现时间为13.


编程中要注意“左移右移”的优先级介于算术运算符和位运算符之间,安全起见,最好加括号。



友情链接: