将只有两种状态的一组对象用二进制进行表示是一种常用建模方法，因此位运算技巧是比较重要的。
位操作经典题目：
37. 解数独 这题的位运算有点秀
剑指 Offer 15. 二进制中1的个数 LCOF 类似于Integer.bitCount()的功能
- 代替数组用来表示字符出现与否/出现次数是奇数还是偶数
模拟小写字典字符，出现与否：
面试题 01.01. Is Unique LCCI
public boolean isUnique(String astr) {
int count = 0;
for (int i = 0; i < astr.length(); ++i) {
int move = astr.charAt(i) - 'a';
if ((count & 1 << move) == 0) {
count |= 1 << move;
} else {
return false;
}
}
return true;
}
模拟小写字典字符（总共26个），使用int类型（32位，每一位记录不同的字符是否出现）足够了。注意题目中，使用|=是可以的，但是+=是不可以的，如果出现次数多可能会出现进位。
模拟128个ASCII字符，统计出现次数是奇数还是偶数：
面试题 01.04. Palindrome Permutation LCCI
用两个long，每一位对应于某一个ASCII字符。并且使用亦或来统计出现次数是奇数还是偶数。
因为long是64位的，int是32位的，所以如果使用long只需要2个分别代表高64位和低64位即可。如果用int则需要4个。
public boolean canPermutePalindrome(String s) {
long highBitmap = 0;
long lowBitmap = 0;
for (char ch : s.toCharArray()) {
if (ch >= 64) {
highBitmap ^= 1L << ch - 64;
} else {
lowBitmap ^= 1L << ch;
}
}
return Long.bitCount(highBitmap) + Long.bitCount(lowBitmap) <= 1;
}
这里有一个易错点，也是long类型使用中的易错点，如果上面代码中的1L写成了1，代码会出错。因为1默认为int类型，只有32位，如果左移的位数超过32，则会从0重新开始。比如'A'是第65个字符， 1左移一位，highBitmap做了亦或之后是2。'a'是第97个字符，1 <<(97 - 64) 相当于1 << 33，因为对于32位的int来说只能左移0-31位，如果是33相当于33%32 == 1，即最后效果是左移一位。这回导致“Aa”会判定某一位出现次数为偶数。
- 判断奇数、偶数
用num&1代替num % 2
-
1的探针：n & (1 << i)
测试n的从右往左数第i位是否为1 -
b & (−b) 得到 bb 二进制表示中最低位的 1。
解释：
two's complement: -b = ~b + 1
我们假设b的二进制表示：111000
-b = ~b + 1， 即000111 + 1 = 001000
111000 & 001000= 001000
直观地来理解一下，~ b和b是完全相反的，+1会使~b最低位的连续的 1 都变为 0，而~b最低位的 0变为 1，从而这些变化的位与原来的b是相同的，位与运算之后会得到保留（即保留了b最低位的连续的 0和b最低位的 1）。
如果想要知道这个1位于从右往左数的哪一位
可以使用
Integer.bitCount(digitMask - 1)
-
mask &= (mask - 1) 抹去最低位的1
mask：101010
mask - 1：101001
mask &= (mask - 1) ： mask = 101000
还有一种操作：
上面我们用b & (−b) 得到了最低位的1，用亦或也可以抹去。
b ^ (b & (−b)) = 111000 ^ 001000 = 110000 -
亦或的巧用
亦或可以用作开关，这点可以参考37. 解数独 。
里面flip方法使用了下面这种亦或
line[i] ^= (1 << digit);
在回溯中连续调用两次，可以打到选中/取消的效果（输入1，原来是0变成1，原来是1变成0）
flip(i, j, digit);
- 一些小坑点：
使用位运算的时候，一定要小心语法错误，等于的判断优先级高于位运算的优先级，因此类似于这种判断是错误的，int不能和boolean进行位运算（先进行了==后进行&）
if (input & (input - 1) == 0)
//应该写成：
if ((input & (input - 1)) == 0)
参考
网友评论