LeetCode 位运算问题

位运算真的是我觉得最讨厌的题目之一了，就不会真是不会，但是另一方面，位运算又该死的优雅，所以还是得练练哈哈

位运算的基础操作

获取第i位 (0或1)

1

n >> i & 1

设置第i位为1

1

n | (1 << i)

设置第i位为0

1

n & (^(1 << i))

获取最低位的1

1

n & (-n)

去掉最低位的1

1

n & (n-1)

LC52 N皇后II

这题其实跟位运算是相关的，我们这样来思考，我们从上到下遍历棋盘，如果能放得下皇后就试试，放不下就终止，这里其实只需要O(1)的空间复杂度就性了，这应该是我遇见过最优雅的位运算了

这里还是需要注意几个事情，每次用bits找到目前还有1的位，就是可以放皇后的位置，然后pick就是选择这个位置，然后更新col，pie，na，其中竖着的col照常，撇pie和捺na要平移一位，然后bits去掉我们选择这个位置，继续遍历，这真的是我见过最优雅的解法之一了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func totalNQueens(n int) int {
    cnt := 0

    var dfs func(row, col, pie, na int)
    dfs = func(row, col, pie, na int){
        if row == n{
            cnt ++
            return 
        }
        bits := ^(col | pie | na) & (1 << n - 1)
        for bits > 0 {
            pick := bits & (-bits)
            dfs(row+1, col|pick, (pie|pick)<<1, (na|pick)>>1)
            bits &= bits-1
        }
    } 

    dfs(0, 0, 0, 0)
    return cnt 
}

LC136 只出现一次的数字

这题其实也是位运算的经典题目，我们只需要遍历数组，然后对每个数进行异或操作，最后的结果就是只出现一次的数字

1
2
3
4
5
6
7


func singleNumber(nums []int) int {
    res := 0
    for _, num := range nums {
        res ^= num
    }
    return res
}

LC137 只出现一次的数字II

这里需要用到两个变量，one和two，分别表示当前位为1和2的次数，然后遍历数组，更新这两个变量，最后返回one就是结果注意一下这里位运算的优先级，^的优先级比&高，所以需要用括号来保证优先级

1
2
3
4
5
6
7
8


func singleNumber(nums []int) int {
    one, two := 0, 0
    for _, num := range nums{
        one = (one ^ num) & ^two
        two = (two ^ num) & ^one
    }
    return one
}

位运算的优先级

优先级从高到低依次是

一元运算符：例如取反^、按位非^、加减+ -等。
乘法、除法、取模等* / %
加减+ -
位移运算符<< >>
按位与&
按位异或^
按位或|
比较运算符== != < <= > >=
逻辑与&&
逻辑或||
赋值运算符= +=等等