位运算相关

Posted on Edited on In Word count in article: 4.5k Reading time ≈ 4 mins.
go的位运算

位运算

与 &

有两个数都是1结果才为1

1
2
3
4
var b uint8 = 20 // 00010100
var c uint8 = 15 // 00001111
a := b & c // 00000100
a = 4

或 |

两个数有一个是1 结果就是1

1
2
3
4
var b uint8 = 20 // 00010100
var c uint8 = 15 // 00001111
a := b & c // 00011111
a = 31

异或 ^

^作二元运算符就是异或，相同为0，不相同为1

1
2
3
4
var b uint8 = 20 // 00010100
var c uint8 = 15 // 00001111
a := b & c // 00011011
a = 27

^作一元运算符表示是按位取反

1
2
3
4
var b uint8 = 20 // 00010100
var c uint8 = 15 // 00001111
a := b & c // 00011011
^a = 228 // 11100100

uint8与int

1
2
3
4
var b uint8 = 20 // 00010100
var c int = 20 // 00010100
^b = 228 // 11101011
^c = -21 // -10101

特殊情况

1
2
3
var b uint8 = 20 // 00010100
b ^ b = 0
b ^ 0 = b

int类型，故最高位是符号位，符号位取反，所以得到的结果是负数

一个有符号位的^操作为 这个数+1的相反数

&^

将运算符左边数据相异的位保留，相同位清零

1&^1 得0
1&^0 得1
0&^1 得0
0&^0 得0

1
2
3
4
var b uint8 = 20 // 00010100
var c uint8 = 15 // 00001111
a := b &^ c
a = 16 // 00010000

以b为准，相异保留b的位，相同，清零b的位

<< 左移 >> 右移

左移规则：右边空出的位用0填补，高位左移溢出则舍弃该高位

右移规则：左边空出的位用0或者1填补。正数用0填补，负数用1填补。注：不同的环境填补方式可能不同。低位右移溢出则舍弃该位

1
2
3
4
5
var b uint8 = 20 // 00010100
a := b << 1
a = 40 // 00101000
c：= b >> 1
c = 10 // 00001010

左移1相当于乘以2
右移1相当于除以2

判断奇偶

同时也是获取最后一位的值

1
2
3
4
var b int = 22 // 10110
a := b & 1
a == 0 // 偶数
a == 1 // 奇数

清0最低位的1

1
2
3
var b int = 22 // 10110
a := b & (b - 1)
a = 20 // 10100

得到最低位的1

1
2
3
var b int = 22 // 10110
a := b & (-b)
a = 2 // 10

将第n+1位置为1

1
2
3
var b int = 22 // 10110
a := b | (1 << 0) // 将第0位置为1,1 << n, 第n位
a = 23 // 10111

将第n+1为置为0

1
2
3
var b int = 22 // 10110
a := b & (^(1 << 1)) // 将第1位置为0,1 << n, 第n位
a = 20 // 10100

将右n位清0

1
2
3
var b int = 22 // 10110
a := b & (^0 << 2)// 将右边2位清0， n，右边n位
a = 20 // 10100

获取第n+1位值

1
2
3
var b int = 22 // 10110
a := (b >> 2) & 1 // 获取第2位值
a = 1 // 1

获取第n+1位的幂值

1
2
3
var b int = 22 // 10110
a := b & (1 << 2) // n=2，其实是从右边数第3位的
a = 4 // 从右边开始算，第一位是0， n

将最高位至第n+1位（含）清0

1
2
3
var b int = 22 // 10110
a := b & ((1 << 3) - 1) // n=3，其实是从左边数到第3位，不含第3位，前面的都清0
a = 6 // 110

例题

颠倒二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func reverseBits(num uint32) uint32 {
    var res uint32 = 0
    for i := 0; i < 32; i++ {
    	// 新数字左移1位
        res <<= 1
        // num & 1是获取num的最后一位，也可以判断奇偶
        // 最后一位加1，用或也可以，因为res最后一位肯定是0
        res |= num & 1
        // 右移1位，更新num
        num >>= 1
    }
    return res
}

// 16位互相交换
func reverseBits(num uint32) uint32 {
    var res uint32 = 0
    for i := 0; i < 16; i++ {
        res |= (num & (1 << i)) << (31 - 2 * i) 
    }
    for i := 16; i < 32; i++ {
        res |= (num & (1 << i)) >> (2 * i -31)
    }
    return res
}

1的个位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 清0次数
func hammingWeight(num uint32) int {
    count := 0
    for num > 0 {
    	// 将最低位的1清0
        num &= num - 1
        count++
    }
    return count
}

// 循环检查
func hammingWeight(num uint32) int {
    count := 0
    for i := 0; i < 32; i++ {
        if (num >> i) & 1 == 1{
            count++
        }
    }
    return count
}

2的幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 得到最低位的1，看是不是等于本身，是这说明就一个1
func isPowerOfTwo(n int) bool {
    if n == 0 { return false }
    return n & (-n) == n
}

// 清0最低位的1，看是不是等于0，是则说明只有1个1
func isPowerOfTwo(n int) bool {
    if n == 0 { return false }
    return n & (n-1) == 0
}

// 非位运算
func isPowerOfTwo(n int) bool {
    if n == 0 { return false }
    for  n % 2 == 0 {
        n /= 2
    }
    return n == 1
}

比特计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 非dp算法
func countBits(num int) []int {
    res := make([]int, num+1)
    for i := 1; i <= num; i++ {
        cur := i
        for cur != 0 {
            cur &= cur - 1
            res[i]++
        }
    }
    return res
}

// 高有效位
func countBits(num int) []int {
    dp := make([]int, num+1)
    hb := 0
    for i := 1; i <= num; i++ {
        // 如果是2的幂，则更新高有效位 
        if i & (i - 1) == 0 { 
            hb = i
        }
        // 高有效位的下一位是+1，以此类推，直到下一个2的幂，并更新
        dp[i] = dp[i - hb] + 1
    }
    return dp
}

// 奇偶数，等于去掉最后一位前面的值 加上新的一位，是奇数就是1，偶数就是0
func countBits(num int) []int {
    dp := make([]int, num+1)
    for i := 1; i <= num; i++ {
        dp[i] = dp[i >> 1] + i & 1
    }
    return dp
}

N皇后

基于位运算的回溯递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 基于位运算的递归
func solveNQueens(n int) [][]string {
    // 最终结果
    res := [][]string{}
    // 初始化一个slice，记录每一行q的位置，初始化都为-1
    bSlice := make([]int, n)
    for i := 0; i < n; i++ {
        bSlice[i] = -1
    }

    var dfs func(int, int, int, int)
    // 递归函数
    // row行。 col列。 dia1.dia2两个对角线
    dfs = func(row, col, dia1, dia2 int) {
        // 递归终止条件,符合规则的一种结果
        if row == n {
            tmp := []string{}
            // 遍历每一行，每一列，初始化都为 .
            for i := 0; i < n; i++ {
                cur := make([]byte, n)
                for j := 0; j < n; j++ {
                    cur[j] = '.'
                }
                // 根据每一行的q的位置，更新q
                cur[bSlice[i]] = 'Q'
                // byte数组转为string加入结果
                tmp = append(tmp, string(cur))
            }
            res = append(res, tmp)
            return
        }
        // 列，两个对角线，或运算(col | dia1 | dia2)，即所有使用了的位置
        // ^对以上结果取反，得到还未使用的位置，即可用的位置
        // (1 << n) - 1)从最高位到第n位，都清0，得到n位二进制
        availP := ((1 << n) - 1) & (^(col | dia1 | dia2))
        // 循环递归，可用位置不为0
        for availP != 0 {
            // 取最低位的可用位置
            p := availP & (-availP)
            // 最低位清0，更新可用位置
            availP &= availP - 1
            // 减去1之后计算1的个数，得到这一行的q的索引位置，也就是p的1在第几位
            // 高位->低位就是bslice从左->右
            bSlice[row] = bits.OnesCount(uint(p - 1))
            // 继续递归。行数+1， 列与最低位的可用位置取或，代表这一位已经使用了
            // 对角线与可用位置取或，再根据对角线方向，一个左移，一个右移
            dfs(row + 1, col | p, (dia1 | p) >> 1, (dia2 | p) << 1)
            // 回溯，这一行的q的位置为-1
            bSlice[row] = -1
        }
    }

    dfs(0, 0, 0, 0)
    return res
}