前言：
一直对位运算只是初步的了解。这次看到一个题利用位运算换取存储空间。写个题解，加深印象。
位运算
1.移位
直接上例子（左移<<）
public class Test {
public static void main(String[] args) {
System.out.println(5<<2);//运行结果是20
}
}
在实际的运算中则是将5转化为二进制再左移两位。（java int 32位为例）
0000 0000 0000 0000 0000 0000 0000 0
101
然后左移2位后，低位补0：
0000 0000 0000 0000 0000 0000 000
1 01
00 换算成10进制为20
同理
public class Test {
public static void main(String[] args) {
System.out.println(1<<3);//运行结果是8
}
}
0000 0000 0000 0000 0000 0000 0000 000
1
0000 0000 0000 0000 0000 0000 0000
1
000
（右移同理）
2.位与（&）
位与：第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
public class Test {
public static void main(String[] args) {
System.out.println(5 & 3);//结果为1
}
}
程序中：
将5化成二进制： 0000 0000 0000 0000 0000 0000 0000 0
101
将3化成二进制： 0000 0000 0000 0000 0000 0000 0000 00
11
将1化成二进制： 0000 0000 0000 0000 0000 0000 0000 000
1
（因为5的第3位为1，3的第三位为0，则结果的第三位就为0，第二位同理。第一位3和5都是1，则就为1。）
3.位或( | )
位或操作：第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
public class Test {
public static void main(String[] args) {
System.out.println(5 | 3);//结果为7
}
}
5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0
101
3转换为二进制：0000 0000 0000 0000 0000 0000 0000 00
11
7转换为二进制：0000 0000 0000 0000 0000 0000 0000 0
111
由位运算操作符衍生而来的有：
&= 按位与赋值 、|= 按位或赋值 、^= 按位非赋值、 >>= 右移赋值、 <<= 赋值左移。
举个栗子:
@Test
public void testBitOperation(){
int a = 8; //1000
a |= 3; //3:11
System.out.println(a); //应该是1011(二进制） 及 11
}
现在来看看具体应用：
题目：
解題思路：
先说下正常的题目思路
：题目的提示说是哈希表但是大小才为9✖9并且每个格子数字不超过9。所以不必用哈希表而是用
数组写题
。题目要求的是每行每列每个3✖3的小方格不能出现相同的数字。所以我们可以先准备
3个二维数组来分别储存行列及小方格值。再利用两次for循环遍历数独
。每次遍历的值，一次性储存在3个值的对应
下标的位置
，并标记。如果下次遍历的数在已有标记则直接返回结果。
直接判断的代码如下：
class Solution {
public boolean isValidSudoku(char board[][]) {
int length = board.length;
//二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
//表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
int line[][] = new int[length][length];
int column[][] = new int[length][length];
int cell[][] = new int[length][length];
for (int i = 0; i < length; ++i)
for (int j = 0; j < length; ++j) {
//如果还没有填数字，直接跳过
if (board[i][j] == '.')
continue;
//num是当前格子的数字
int num = board[i][j] - '0' - 1;
//k是第几个单元格，9宫格数独横着和竖着都是3个单元格
int k = i / 3 * 3 + j / 3;
//如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
//举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
return false;
//表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
line[i][num] = column[j][num] = cell[k][num] = 1;
}
return true;
}
}
运算结果：
位运算解法：
因为这题只需要9位而java
Int类型是4个字节占的是32位远远大于9位
，所以我们完全可以不用二维数组，而是用一维数组，再转化为二进制，利用位运算进行标记。
比如示例1中的第二位数是3
，在直接判断的方法存储是（下标-1）：
line[0][2] = column[1][2] = cell[0][2] = 1;
换成二进制则写法则是：
(因为二级制利用1来标记，所以1左移3位为1000则为8）
column[1] |= 8;
line[0] |= 8;
cell[0] |= 8
此时后续判断3这个值是否存在只要判断这个位上是否有1。代码如下：
if ((column[i] & 8) > 0 || (line[0=j] & 8) > 0 || (cell[k] & 8) > 0)
return false;
所以相当于本来需要用二维数组，现在用一维数组就可以搞定。多出的步骤只是把十进制转二进制储存。
真正储存的形式变为从十进制变成二级制储存与判断。
代碼:
附上完整代码（参考）：
public boolean isValidSudoku(char[][] board) {
int[] line = new int[9];
int[] column = new int[9];
int[] cell = new int[9];
int shift = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
//如果还没有填数字，直接跳过
if (board[i][j] == '.')
continue;
shift = 1 << (board[i][j] - '0');
int k = (i / 3) * 3 + j / 3;
//如果对应的位置只要有一个大于0，说明有冲突，直接返回false
if ((column[i] & shift) > 0 || (line[j] & shift) > 0 || (cell[k] & shift) > 0)
return false;
column[i] |= shift;
line[j] |= shift;
cell[k] |= shift;
}
}
return true;
}
运行结果：
如有不足，敬请指正~