对于大多数人来说位操作的知识应该都早就还给老师了,所以刷lc的bit op类题会有些负担,所以简单介绍下lc里关于bit op需要的知识。

首先是基本的操作 & |,这个即使还给老师也很容易想起来,跟我们常用的逻辑操作符基本一致:

1 & 1 = 1
1 & 0 = 0
1 | 0 = 1
1 | 1 = 1

异或操作可能需要回忆一下:

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0

所以从异或的特点可以得出两个结论:n^n=0,n^0=n。

这个结论适用于 LC136,数组中每个数字都出现两次,只有一个出现一次,找到出现一次的数字:

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

基本一样的还有LC389

接下来是左移和右移操作 << >>:

0001<<1 = 0010
1000>>1 = 0100

这个使用的时候要注意不要溢出,同时也可以得出结论<<一次相当于*2,>>一次相当于/2。

同时我们可以基于这个特性来写出一个按位操作的方法:

// 最大不超过32bit
for i:=31;i>=0;i--{
  1<<i
}

以上代码可以用来按位比较对应的bit,因为每次循环对1进行移位操作后结果的值如下:

0010000
0001000
0000100
0000010
0000001

该方法可以适用于LC461, LC476等,看一下LC476的解法:

func findComplement(num int) int {
    flag:=false
    for i:=31;i>=0;i--{
        // 从最高位开始找到不为0的第一个
        if (num & (1<<uint(i)))!=0 {flag = true}
        // 对该位跟1进行异或
        if flag {num ^= (1<<uint(i))}
    }
    return num
}

LC461可以用同样的方式得出答案,先对x,y异或然后计算1的个数即可。

不过对于计算一个数字n二进制表达中1的个数我们可以有另一种算法,先看下面的例子:

n   = 100000
n-1 = 011111
n & n-1 = 0

n   = 101000
n-1 = 100111
n & n-1 = 100000

所以只要在n不为0的时候每次对n与n-1进行&操作就可以消掉最右侧的一个1,所以对于LC461答案如下:

func hammingDistance(x int, y int) int {
    res:=0
    tmp:=x^y
    for tmp!=0{
        res++
        tmp &= (tmp-1)
    }
    return res
}

还有单独计算1个数的LC191, 解法跟上面基本一致。

同样是计算二进制数字中1的个数,来看一下LC381,这个题要求的苛刻之处在于线性时间,所以不能用上述方法对每一个进行计算,不过依旧可以用到上面的结论。

n   = 110   // 6
n-1 = 101   // 5
n & n-1 = 100 // 4

对于n来说,n里面1的个数会比n&n-1里面1的个数,如上,所以6里面1的个数就是4的1的个数+1,所以答案如下:

func countBits(num int) []int {
    res:=make([]int,num+1)
    res[0] = 0
    for i:=1;i<=num;i++{
        res[i] = res[i&(i-1)]+1
    }
    return res
}

对于计算二进制位中1的个数还有一道LC762,这个的限定了左右区间同时还要求计算1的数量是不是质数,对于计算1的个数没办法像上面那样优化了,因为L的起点就可能很大,所以计算1的个数的方法还是用上面最开始的方式。

不过对于判断质数这道题还是有个小细节的,那就是说给定了最大值范围,这个最大值范围最多不超过20bit就可以完全表示了,所以可以先把20以内的质数缓存一下然后对比个数即可,不需要计算是不是质数:

func countPrimeSetBits(L int, R int) int {
    c :=0
    m:=map[int]bool{
        2: true,
        3: true,
        5: true,
        7: true,
        11: true,
        13: true,
        17: true,
        19: true,
    }
    count:=func(n int) int{
        res:=0
        for n!=0{
            res++
            n = n&(n-1)
        }
        return res
    }

    for i:=L;i<=R;i++{
        if m[count(i)] {
            c++
        }
    }
    return c
}

还有一个类似的LC231,这道题让我们判断一个数字是不是2的幂,上面也已经介绍过<<一次就相当于*2,所以如果一个数字是2的幂必然只有一位是1,其他位数都是0,如下:

1 0001
2 0010
4 0100
8 1000

所以可以简单的使用计算有多少个1的方法查看是否满足只有1个1的情况:

func isPowerOfTwo(n int) bool {
    return (n > 0) && ((n & (n - 1)==0))
}

同样的还有LC342,这道题让我们判断是不是4的幂,跟上一道题一样,首先确定4的幂必然也是2的幂,其次就是可以看一下符合4的幂的特点:

1  000001
4  000100
16 010000

对比2的幂来说,就是1是每次左移两位,所以1永远在奇数位上,所以我们只需要想办法判断1在奇数位上即可

1 000001
2 000010
n 010101
1 & n = 1
2 & n = 0

所以找到N即可,这个结论其实就有点trick了,因为奇数位都是1的值是0x55555555,所以答案如下:

func isPowerOfFour(num int) bool {
    return num>0 && (num & (num-1))==0 && (num & 0x55555555) == num
}

然后可以看一下LC693,这道题就是让我们判断一个数字的二进制是不是01交替的,我们可以用上面循环的方法来判断每一位,不过也可以找一下规律:

n        01010101
n>>1     00101010
n+n>>1   01111111
n+n>>1+1 10000000
&        00000000

这个特点主要是凑够一个全是11111的二进制表达,对于全是1的二进制表达只要&+1就应该是0

func hasAlternatingBits(n int) bool {
    return ((n + (n >> 1) + 1) & (n + (n >> 1))) == 0
}

其他的一些有关bit op的题都是基础操作+其他算法例如回溯,dp等等,就不单独介绍了,LC的bit op题列表如下:

https://leetcode-cn.com/list/ohidzdd