算法笔记之位运算实现复合状态

位运算的用途之一，实现复合状态，每一位代表一个状态。

LeetCode 289. 生命游戏

题目描述：根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

进阶：你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。

解题思路：本题不是很难，但是要求使用原地算法，这就要求我们既能知道旧状态，又能得到新状态，我们使用两位二进制数字代表新旧状态。

Java代码：

public void gameOfLife(int[][] board) {
        if(board.length == 0 || board[0].length == 0) {
            return;
        }
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                computeNewState(board, i, j); // 修改为复合状态
            }
        }

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                board[i][j] = board[i][j] >> 1;
            }
        }
    }

    private void computeNewState(int[][] board, int x, int y) {
        int live = 0;
        int dead = 0;
        int oldState = -1;
        for(int i = x - 1; i <= x + 1; i++) {
            for(int j = y - 1; j <= y + 1; j++) {
                int c = getOldState(board, i, j);
                if(x == i && y == j) {
                    oldState = c;
                } else {
                    if(c == 1) {
                        live++;
                    } else if(c == 0) {
                        dead++;
                    }
                }
            }
        }
        int newState = -1;
        // 判断新状态
        if(oldState == 1) {
            if(live < 2) {
                newState = 0;
            } else if(live == 2 || live == 3) {
                newState = 1;
            } else if(live > 3) {
                newState = 0;
            }
        } else {
            if(live == 3) {
                newState = 1;
            } else {
                newState = 0;
            }
        }
        //复合状态
        board[x][y] = (newState << 1) + oldState;
    }

    // 获取细胞状态，不在范围内则返回-1
    private int getOldState(int[][] board, int x, int y) {
        if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return -1;
        }
        return board[x][y] & 1; // 获取最低位
    }