有趣的位演算 - 翻转整数位

有趣的位运算 - 翻转整数位
最直接的想法可能是这样：

public static int reverse(int num){int result = 0;for(int i=0; i<32; ++i){if((num & (1<<i))>0)result |= 1<<(31-i);}return result;}

上面的方法虽然直观，但却不是高效的，于是（实测效率差10倍左右 : )）：

public static int reverse(int i) {      // HD, Figure 7-1      i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;//交换相邻的两个位      i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;//交换相邻的两个两位    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f; //交换相邻的两个四位    i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;//交换相邻的两个八位    i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;//交换相邻的两个十六位    return i;  }

初看有些头晕，其实也很好理解:
0x55555555：每个16进制对应4位2进制，5对应0101，所以0101,0101,0101,0101,0101,0101,0101,0101
0x33333333：0011,0011,0011,0011,0011,0011,0011,0011
0x0f0f0f0f：0000,1111,0000,1111,0000,1111,0000,1111
....
i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;    //交换相邻的两个位 
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;    //交换相邻的两个两位
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f; //交换相邻的两个四位
i = (i & 0x00ff00ff) << 8 | (i >>> 8 ) & 0x00ff00ff;    //交换相邻的两个八位
i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;//交换相邻的两个十六位

而这5步则实现了将一个整数的32位分部分对换的过程

而JDK的设计人员则更简洁的实现：

public static int reverse(int i) {      // HD, Figure 7-1      i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;      i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;      i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;      i = (i << 24) | ((i & 0xff00) << 8) |          ((i >>> 8) & 0xff00) | (i >>> 24);      return i;  }

将方法2的最后两步合并，直接将低8位移为高8位，高8位无符号右移为低8位，中间的16位互换

查看更多 下一篇