位运算总结

由于计算机存储数据都是以二进制的形式存储，位运算实质时对二进制数进行操作。在做题目的的时候，通过位运算处理数据速度很快，便能使缩短计算时间。

1. 位运算的种类

2. 使用技巧

1)判断奇偶

只需要个位数判断是0还是1

1
2
3
4
5
6

if(a & 1){  //相当于a % 2 == 1
    cout << "a是奇数" << endl;
}
else{
    cout << "a是偶数" <<endl;
}

2)交换两数

不需要引入第三方变量

1
2
3
4
5

void Swap(int &a, int &b){
    a ^= b;  //a = a^b; 复合操作
    b ^= a;
    a ^= b;  
}

3) 符号变换

负数变正数，正数变负数，只需要取反加一

1
2
3

int signReversal(int a){
	return ~a + 1;
}

4) x & (-x)表示什么

-x 代表 ~x+1（x取反再加1，负数在二进制中是正数的补码表示，补码是反码+1）

lowbit = x & -x 可以算出从右到左第一个1出现的位置，如6 & (-6) =110 & (010)= 010。

• x = 0，结果为0
• x 是奇数，结果为1
• x是偶数，结果是2最大次方的因子。（如x=28,2^4^=16,故为4）

5) x&(x-1)表示什么

• 每次与运算会把最低位的1去掉，用于统计一个数的二进制1的个数。

  1 2 3 4 5 6 7 8 9

  // num = 7（111）, 则输出3 func hammingWeight(num uint32) int { cnt := 0 for num != 0 { num = num & (num - 1) cnt++ } return cnt }

• x&(x-1) == 0，即x为2的幂次

6) c ^= 1<<5

ASCII 码中 a为97，A为65，中间差了32，而2^5^=32，因此一个字符c 异或 左移5位可以表示大小写之间的转换。

7）^= 异或

根据异或性质，可以把出现2次的数消除掉

1
2
3
4
5
6
7
8
9

// nums = [1,1,2,3,3,4,4,8,8] 数组中只有一个数字出现一次，其余都出现2次。要找出只出现一次的数字
func singleNonDuplicate(nums []int) int {
    ans := 0
    //  出现2次会消除
    for _, x := range nums {
        ans ^= x
    }
    return ans
}

将a加入集合

1

orset |= a

将a移出集合

1

orset ^= a

8) 格雷码 i ^(i>>1)

任意两个（包括首尾）相邻的数只有一位二进制数不同，这种编码方式就是格雷码，如3,2,0,1 。见LC1238. 循环码排列

9）位运算和集合论

集合可以用二进制表示，二进制从低到高位1表示在集合中，0表示不在集合中。例如集合{1,2,4}用二进制可以表示为10110。

9.1 判断元素d是否在集合mask中，如果为1则在集合中，为0则不在

1

mask >> d & 1

9.2 把元素d添加到集合mask中

1

mask | (1 << d)

9.3 求两个数组的交集

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

// minNumber([]int{3, 5, 2, 6}, []int{3, 1, 7})
// 数组对应的二进制位图是
// 101100 &  10001010 = 1000, 0的个数就是交集的值

func minNumber(nums1 []int, nums2 []int) int {
	mask1, mask2 := 0, 0
	for _, x := range nums1 {
		mask1 |= 1 << x

	}
	for _, x := range nums2 {
		mask2 |= 1 << x
	}
	fmt.Println(mask1 & mask2) // 1000，0的个数就是交集的值，此处为3
	if mask1&mask2 != 0 {
		return bits.TrailingZeros(uint(mask1 & mask2))
	}
	x, y := bits.TrailingZeros(uint(mask1)), bits.TrailingZeros(uint(mask2))
	return min(x*10+y, y*10+y)
}

10) -1和任何数AND运算都是那个数

1
2
3
4
5
6
7
8
9
10
11
12
13

# LC2871. 将数组分割成最多数目的子数组
int maxSubarrays(vector<int>& nums) {
        int ans = 0;
        int a = -1;
        for(int x : nums) {
            a = a & x;
            if(a == 0) {
                ans++;
                a = -1;
            }
        }
        return ans == 0 ? 1 : ans;
    }

• ← Previous Post
• Next Post →