位运算应用和工具

有时需要追求效率，会代替一些算术运算。

• 求商：a >> n  <=>  a / 2^n
• 求积：a << n  <=>  a * 2^n
• 求余：a & ((1 << n) - 1)  <=>  a % 2^n
• 奇偶判断：a & 1 == 1  <==>  a % 2 == 1

一般1表示选中或者开启项，0表示未选或者关闭项。

• 获取全部项：(1 << n) - 1
• 获取指定项：1 << idx
• 获取反选项：~a
• 开启指定项：a |= b
• 合并两选项：a | b
• 关闭指定项：a &= ~b
• 查看公共项：a & b
• 保留公共项：a &= b
• 切换指定项：a ^= b
• 查看改变项：a1 ^ a2
• 查看未变项：~(a1 ^ a2) = ~a1 ^ a2 = a1 ^ ~a2

输出组合，如下示例，输出abcd的组合。

public static void main(String[] args) {
    char[] chars = "abcd".toCharArray();
    int len = chars.length;
    
    int bits = (1 << len) - 1;
    for (int i = bits; i > 0 ; i = (i - 1) & bits) {
        System.out.printf("%" + len + "s：", Integer.toBinaryString(i));
        for(int j = 0; j < len; j++) {
            if(((i >> j) & 1) == 1)
                System.out.print(chars[j]);
        }
        System.out.println();
    }
}

输出结果：

1111：abcd
1110：bcd
1101：acd
1100：cd
1011：abd
1010：bd
1001：ad
1000：d
 111：abc
 110：bc
 101：ac
 100：c
  11：ab
  10：b
   1：a

位移注意事项：

• >>是带符号右移，即正数时左边补0，负数时左边补1。
• >>>是无符号右移，即总是左边补0。

Long.bitCount(long)，Integer.bitCount(int)：计算1的数量。

BitSet：用于表示可以比long更长的存储位数。

• int cardinality()，计算1的数量。
• and(BitSet)，与运算，即保留公共项，a &= b。boolean intersects(BitSet)，判断是否存在公共项。
• or(BitSet)，或运算，即开启指定项，a |= b。
• xor(BitSet)，异或运算，切换指定项，即a ^= b。flip(...)，切换指定项，即a ^= b。
• andNot(BitSet)，与非运算，即关闭目标项，a &= ~b。
• int length()，获取长度。boolean isEmpty()，判断长度是否为0。
• set(...)，开启指定项。clear(...)，关闭指定项。set(..., boolean)，设置指定项的值。clear()，关闭所有项，并清空，即长度重置为0。
• boolean get(int)，获取指定项的开关值。
• int previousSetBit(int)/int nextSetBit(int)：从指定位置开始查找上一个/下一个开启项的索引。
• int previousClearBit(int)/int nextClearBit(int)：从指定位置开始查找上一个/下一个关闭项的索引。
• BitSet get(int, int)：截取子集。
• 构造：s+valueOf(ByteBuffer/byte[]/LongBuffer/long[])
• 转换：toLongArray()/toByteArray()

参考文章：http://blog.csdn.net/u011039332/article/details/49967559