算法：位运算

一、引言 §

学计算机最早一般会了解 Byte（字节） 和 Bit（位） 的区别。笔者还还得当年研究生面试的时候，导师看我是跨专业的比较担心，还真的问到我这个问题。

位运算在面试中不多见，但是在算法中用到往往会加分比如本文例子中用来记录选择。比起其他高级数据结构比如 Set、Array 和 List，空间复杂性更友好。

二、基本运算 §

位运算的与、或、非、异或、取反这里就不具体说明，记得不要跟逻辑运算符搞混就好了。另外负数在计算机中通过补码来表示（取反+1）。

下面是一些位运算基本的用法。

1. 判断奇偶性： X & 1 == 1 => 奇数，== 0 => 偶数
2. 把最低位的 1 清 0 => X = X & (X-1)
3. 得到最低位的 1 比如 1100 返回 100 => X & -X
4. 把 X 最右边的 n 位清 0 => X & (~0 << n)
5. 获取 X 的第 n 位值 => (X >> n) & 1
6. 获取 X 的第 n 位的幂值 => X & (1 << (n-1)) ???
7. 仅将第 n 位置为 1 => X | (1 << n)
8. 仅将第 n 位置为 0 => X & (~(1 << n))
9. 将 X 最高位至 n 位（含）清 0 => X & ((1 << n) - 1)
10. 将第 n 位至第 0 位（含）清 0 => X & (~((1 << (n + 1)) - 1))
11. 异或特性 X ^ 0 = X X ^ 1(全 1) = ～X（取反），1（全 1）= ～0 X ^ (~X) = 1(全 1) X ^ X = 0 交换率 => a ^ b = c => a ^ c = b, b ^ c = a 结合律 => a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

三、解决问题例子 §

这里举一个求解八皇后所有解法个数的问题。国际象棋中的八皇后问题指的是在一个 8 X 8 的棋盘上，每行摆一个皇后，不冲突的情况下求一共有多少种摆法。皇后能攻击在同一行、同一列、正斜线、反斜线上的所有其他棋子（包括皇后），所以这是约束条件：摆放好的八皇后不能在同一行、同一列、正斜线和反斜线上。

八皇后简单解法是回溯法。每行有 8 种选择（从第1到第8列），如果皇后之间没有冲突则递归调用到下一行，直到最后一行找到一个可行解，否则提前退出回溯其他选择。

采用位运算也可以求解所有的解法。

package org.stone.study.algo.ex202402;  
  
import java.util.Arrays;  
  
/**  
 * 分别采用位运算和回溯法求解八皇后的所有解法个数问题  
 */  
public class EightQueen {    
    public EightQueen(int n) {  
        this.n = n;  
    }  
    
    public static void main(String[] args) {  
        EightQueen eightQueen = new EightQueen(8);  
        // 八皇后所有解为92个  
//         int count = eightQueen.dfs1(0, 0, 0, 0);  
        int count = eightQueen.backtrack();  
        System.out.println("count:" + count);  
    }  
  
    /**  
     * 位运算方式计算八皇后的解法个数  
     * @param row：当前行数  
     * @param col：一个整数表示所有列上放置皇后的情况  
     * @param pie：一个整数表示所有斜线上放置皇后的情况  
     * @param na：一个整数表示所有反向斜线上放置皇后的情况  
     */  
    public int dfs1(int row, int col, int pie, int na) {  
        int count = 0;  
        if(row == n) {  
            return 1;  
        }  
  
        // 一共有多少个位置可以放  
        int bits = (~(col | pie | na)) & ((1 << n) - 1);  
  
        while(bits > 0) {  
            // 取最后一个 1 表示的数  
            int bit = bits & -bits;  
            // pie 下一行左移1位的位置已经被占用了，na 下一行右移1位的位置也被占用了  
            count += dfs1(row + 1, col | bit, (pie | bit) << 1, (na | bit) >> 1);  
            // 这个位置已经被选择过了，需要去掉  
            bits = bits & (bits - 1);  
        }  
  
        return count;  
    }  
  
    /**  
     * 回溯法求解 N 皇后的解法个数  
     * @return  
     */  
    public int backtrack() {  
        int[][] board = new int[8][8];  
        for(int i = 0; i < 8; i++) {  
            Arrays.fill(board[i], 0);  
        }  
  
        return dfs2(board, 0);  
    }  
  
    public int dfs2(int[][] board, int row) {  
        if(row == n) {  
            return 1;  
        }  
  
        int count = 0;  
        for(int j = 0; j < n; j++) {  
            //剪枝 + 回溯  
            if(validMove(board, row, j)) {  
                board[row][j] = 1;  
                count += dfs2(board, row + 1);  
                board[row][j] = 0;  
            }  
        }  
  
        return count;  
    }  
  
    /**  
     * 判断当前走的一步是否合法：列上没有皇后；左上斜线没有皇后；右上斜线没有皇后  
     * @param board  
     * @param row  
     * @param col  
     * @return  
     */  
    private boolean validMove(int[][] board, int row, int col) {  
        // 同一列上不能有皇后  
        for(int i = 0; i < row; i++) {  
            if(board[i][col] == 1) return false;  
        }  
  
        // 左上的反斜线上不能有皇后  
        for(int i = row - 1, j = col -1; i >= 0 && j >= 0; i--,j--) {  
            if(board[i][j] == 1) return false;  
        }  
  
        // 右上的反斜线上不鞥有皇后  
        for(int i = row -1, j = col + 1; i >= 0 && j < n; i--, j++) {  
            if(board[i][j] == 1) return false;  
        }  
  
        return true;  
    }  
}

四、总结 §

位运算在算法中是比较 tricky 的存在，比如判断奇偶性、乘法等能提高算法运行的效率。更复杂一点的算法中，通过 bit 位记录所有可能的选择，再依次遍历判断选择是否是合法解，会让算法理解起来简单，空间占用更少，这里不展开。

应用层面使用位运算的例子有布隆过滤器，Redis 中的位图等。这些主要是提高空间复杂度为主，同时位运算对提高程序性能也更友好。