首页 > 代码库 > 二进制逆序
二进制逆序
要求计算二进制(16位)的逆序,如数12345用二进制表示为:
00110000 00111001
将它逆序,我们得到了一个新的二进制数:
10011100 00001100
最容易想到的方法就是依次交换两端的数据,从右向左遍历数字,当i位遇到1时,将逆序数字对应的(17-i)位设为1。
def reverseBinary(num): print bin(num) new=0 tmp=(1<<15) for i in xrange(16): if num&1: new|=tmp tmp>>=1 num>>=1 return new if __name__==‘__main__‘: print bin(reverseBinary(12345))>>> 0b00110000001110010b1001110000001100
还有一种高低位互换类似于合并排序的解法。
设想一下,逆序‘ab‘,为‘ba‘。
逆序abcd,可以先两两交换为cdab,然后一一交换为dcba。
逆序abcdefgh,先四四交换efghabcd,然后两两交换fehgcdab,然后一一交换efghdcaba。
那么可以推广到二进制表示:
第一步:每2位为一组,组内高低位交换
00 11 00 00 00 11 10 01
-->00 11 00 00 00 11 01 10
第二步:每4位为一组,组内高低位交换
0011 0000 0011 0110
-->1100 0000 1100 1001
第三步:每8位为一组,组内高低位交换
11000000 11001001
-->00001100 10011100
第四步:每16位为一组,组内高低位交换
0000110010011100
-->1001110000001100
高低位互换时操作大概就是偶数位左移1位,奇数位右移1位
原 数 00110000 00111001
奇数位 0_1_0_0_ 0_1_1_0_
偶数位 _0_1_0_0 _0_1_0_1
其余位数用0填充,然后将奇数位右移一位,偶数位左移一位,此时将这两个数据做按位与运算,即可以达到奇偶位上数据交换的效果了:
def reverseBinary(a): a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1) a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2) a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4) a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8) return aif __name__==‘__main__‘: print bin(reverseBinary(12345))