Bit Manipulation

基本的骚操作

操作	代码实现
Rightmost bit	rmb = x & (-x)
i-th least significant bit	lsb = x & (1 << i)
Set i-th lsb	x = (x | (1 << i))
Reset i-th lsb	x = (x & (~(1 << i)))
Flip i-th lsb	x = x ^ (1 << i)
Power of Two	return (x & (x - 1)) == 0

经典题目

289 Game of Life

因为要做 in-place，又不能直接在原数据上改，所以考虑将原来的一位数据改为两位数据，高位保存新的数据，低位保存旧的数据。

class Solution {
    // 利用移位的方式，进行state的存储与变换，进而实现in-place.
    private int[][] dir = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    public void gameOfLife(int[][] board) {
        // number of neighbors : 8
        // if live number < 2 :       cur live -> die   
        // if live number == 2 or 3 : cur live -> live
        //                ==      3 : cur die  -> live
        // if live number > 3 :       cur live -> die
        
        // 00: death <- death (initial state)
        // 01: death <- live  (initial state)
        // 10: live  <- death
        // 11: live  <- live
        
        int n = board.length;
        if(n == 0) return;
        int m = board[0].length;
        if(m == 0) return;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int lives = getLiveNeiNumber(board, i, j, n, m);
                if(board[i][j] == 1 && lives >= 2 && lives <= 3) {
                    board[i][j] = 3;
                }
                if(board[i][j] == 0 && lives == 3) {
                    board[i][j] = 2;
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] >>= 1;
            }
        }
    }
    
    private int getLiveNeiNumber(int[][] board, int r, int c, int n, int m) {
        int count = 0;
        for(int i = 0; i < 8; i++) {
            if(r + dir[i][0] >= 0 && r + dir[i][0] < n && c + dir[i][1] >= 0 && c + dir[i][1] < m 
               && ((board[r + dir[i][0]][c + dir[i][1]] & 1) == 1)) {
                count++;
            }
        }
        return count;
    }
}

Palindrome Permutation (CC189)

/*
    Method 1: Use an 32-bit integer to record counts as an array.
*/

// Time Complexity: O(N)
// Space Complexity: O(1)

// 1: To check a number has exactly one 1 in binary form: x & (x - 1) == 0
// 2: English alphabet only has 26 distinct letters, 
//    thus we can use a single integer as a bit vector.

public boolean solution(String s) {
    // Assume the string is an ASCII string and contains only lower case letters.
    int bit_vector = 0;
    for(char c : s.toCharArray()) {
        int val = c - 'a';
        int mask = 1 << val;
        if((bit_vector & mask) == 0) {
            bit_vector |= mask;
        } else {
            bit_vector &= ~mask;
        }
    }
    return bit_vector == 0 || (bit_vector & (bit_vector - 1)) == 0;
}

Insertion (CC189)

// EXAMPLE
// Input: N = 10000000000, M = 10011, i = 2, j = 6
// Output: N = 10001001100

public int solution(int n, int m, int j, int i) {
    int allOnes = ~0;
    
    // 1s before position j, then 0s.
    int left = allOnes << (j + 1);
    
    // 1s after position i.
    int right = ((1 << i) - 1);
    
    int mask = left | right;
    
    // clear bits j through i
    int n_cleared = n & mask;
    int m_shifted = m << i;
    
    return n_cleared | m_shifted;
}