小毛的胡思乱想
最近有人问些逻辑位移，算术位移的区别和应用场景，翻了一些旧材料，重新整理一下发出来，给大家欣赏一下java源码中涉及的位操作技巧，摘取的是Integer的源码实现。
整数二进制左边1最早出现的位置
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
画个图简单说明一下计算的原理，简化一下只用8位为例，做了右移1,2,4位之后的效果，最终的效果就是在最早出现1的位置后面都是1。 32位的int也是类似的，最终的效果就是从左边第一位是1开始后面都是1。
有点神奇，仔细想想，前面的多次移位就是最前面那个1填满后面所有位(无论后面是0还是1)。
整数二进制右边1最早出现的位置
public static int lowestOneBit(int i) {
// HD, Section 2-1
return i & -i;
}
负数以补码形式存在，一个负数的补码，就是对应整数的二进制再取反加一。i和-i总有一个是正数，假设是i吧，由于两个数相加是0，在二进制角度来看，假设i最右边出现1的位置是k，那么在相同位置上-i必定也是1，并且-i在k以后的位也是0，这2位相加是0，并且进位1，那么要是k-1位相加得到0，两个数字在k-1位上只能是一个1，另外一个是0，以此类推，可以得到从左边第一位开始直到k-1位都是不同的。两个数进行与运算，只会在k位保留1，其他位都变成0。
整数二进制左边开头有连续多少个0
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
以移动16位为例子，如果左移16位之后是0，那么前16位都是0，那么就只要判断后面16位就可以了。 如果不是0，那么只要判断前面16位就可以了，和前面的区别就是，它不需要移位。后面的移位操作，以此类推就可以了。
整数二进制右边结束有连续多少个0
public static int numberOfTrailingZeros(int i) {
// HD, Figure 5-14
int y;
if (i == 0) return 32;
int n = 31;
y = i <<16; if (y != 0) { n = n -16; i = y; }
y = i << 8; if (y != 0) { n = n - 8; i = y; }
y = i << 4; if (y != 0) { n = n - 4; i = y; }
y = i << 2; if (y != 0) { n = n - 2; i = y; }
return n - ((i << 1) >>> 31);
}
和上面的差不多，假设右移16位不等于0，那么说明只需要判断右边16位就可以了。如果等于0，那说明要判断左边16位。后面的移位操作，以此类推就可以了。
整数二进制总共有多少个1
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
这个算法我是看呆了，神乎其技，它的做法是分别计算每2位，每4位，每8位，每16位，每32位..这样的顺序计算。
以第一行为例，0x55555555刚好每2位是01，而每2位有4种情况，分别是00,01,10,11, 计算i-((i»>1) & 01) 可以得到00,01,01,10, 就对应表示1的个数。是不是很神奇。
整数向左滚动X位
public static int rotateLeft(int i, int distance) {
return (i << distance) | (i >>> -distance);
}
这是基本的移位操作，注意的是右边要采用算术右移。
整数向右滚动X位
public static int rotateRight(int i, int distance) {
return (i >>> distance) | (i << -distance);
}
和上面的一样，就不再详述了。
整数二进制反转
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位交换，第三行是每4位交换，假设原来是b1b2b3b4b5b6b7b8,那么三行执行后，结果就是b8b7b6b5b4b3b2b1，就是一个字节的位进行反转了。最后一句就是按字节反转一下，最终结果就是按位反转了。
整数的符号,0返回0,正数返回1,负数返回-1
public static int signum(int i) {
// HD, Section 2-7
return (i >> 31) | (-i >>> 31);
}
感觉这个实现有点多此一举，直接大小判断很简单，也很直观，为什么不采用?
还是画个图说明一下吧。
整数按字节反转
public static int reverseBytes(int i) {
return ((i >>> 24) ) |
((i >> 8) & 0xFF00) |
((i << 8) & 0xFF0000) |
((i << 24));
}
这个算法很好理解，第一个字节右移24位就跑到第四个字节去了，第二个字节右移8位到了第三位，和FF00与运算就抹掉对第四个字节的影响。后面的就不解释了。
从Integer的方法实现看，有些位操作的技巧实在很巧妙，能想出来真的不容易。像java之类的源代码还是有很多有趣，实用的技巧的，有机会再分享一些。