2. 位运算的知识点以及常用技巧

发表于 更新于 分类于

位运算：

& （与）

eg: 

1
2
3
1 0 1 
0 0 1 
0 0 1

| （或）

eg: 

1
2
3
1 0 1 
0 0 1 
1 0 1

^ （异或）

运算规则：（不进位加法）

1
2
3
4
0          0 ——> 0  
1          0 ——> 1
0          1 ——> 1  
1          1 ——> 0

不进位的加法

1 ^ 1 ==> 0 正常的话：1 + 1 = 20b,但是只看个位, 因此, 取0

运算法则：

  1. 交换律

  2. 结合律

    即$(a^b)^c == a^{b^c}$

  3. 对于任何数x, 都有

    $x^x=0, x^0=x$

  4. 自反性：

    A XOR B XOR B = A xor 0 = A

~ （取反）

  • 把 0 变成 1
  • 把 1 变成 0

<< （左移）

eg:

1
2
1101 << 1 ===> 11010
1 << n  <==>    2^n （向上取整）

>> （右移）

eg:

  • 1101 >> 1 <==> 110

  • n >> x <==> $n \over 2^x$(向下取整)

技巧：

x + (-x)

经验：

  • 将数组无穷大：memset(nums, 0x3f, sizeof(nums))
  • 竞赛中少使用 #include <bits/stdc++.h> // 原因：编译的时间过长,时间会超时
  • 转化成 long long 的形式：乘以 1ll,例子见——>快速幂算法模板—求 $a^b%p$
  • 将大数组放到全局变量中

快速幂算法模板

求 $a^b$

1
2
3
4
5
6
7
8
9
10
11
long long quickPower(int a, int b)
{
    long long res = 1;
    while(b) {
        if(b & 1)
            res *= 1ll * a;
        a *= a;
        b >>= 1;
    }
    return res;
}

求 $a^b%p$

1
2
3
4
5
6
7
8
9
10
11
12
int quickPowerMod(int a, int b, int p)
{
    int res = 1 % p;
    while(b) {
        if(b & 1)
            res = res * 1ll * a % p;
        a = a * 1ll * a % p;
        b >>= 1;
    }
    return res;
}

模运算法则

1
2
3
4
5
6
7
(a + b) % p = (a % p + b % p) % p

(a - b) % p = (a % p - b % p) % p 

(a * b) % p = (a % p * b % p) % p 

(a^b) % p = ((a % p)^b) % p

位运算常用技巧

用异或来实现配偶

1
2
3
4
5
0, 1
2, 3
4, 5
6, 7
……

即(把每个整数异或一个1, 就可以得到他的配偶)

1
2
3
4
0 ^ 1 = 1,            1 ^ 1 = 0
2 ^ 1 = 3,            3 ^ 1 = 2
……
2k ^ 1 = 2k + 1,    (2k + 1) ^ 1 = 2k

用法

一般在图论里面, 写最小费用流时, 我们会存一个编的正向编和反向编, 会需要快速求出来一个数的反向编是什么

lowbit运算(树状数组的基础)

定义

快速的求出来整数n, 在二进制表示里面, 最低的一位1是哪个(或者说：n的二进制表示中最右边一个1)

效果

lowbit(1110011000) ——> 1000

实现

1
2
3
4
5
首先, 假设n的二进制是1110011000
然后, 对n取反, 得到：~n = 0001100111
接着, ~n+1  ===>  0001101000
紧接着, (~n + 1) & n ===> 0000001000 ===> 1000
最后, 由于-n = ~n + 1,所以lowbit就是：(-n) & n

代码实现

1
2
3
4
int lowbit(int n)
{
    return (-n) & n;
}

拓展

  1. 复杂度和1的个数有关和

  2. 可以快速求出来一个整数里面有多少个1

  3. 求n是2的整次方幂

    解析:
    $$
    2^n == 1 << n
    $$

    $$
    n & (-n) == n
    $$

    $$
    otherwise, n & (-n) < n
    $$

原码、反码、补码

正数

原码, 反码, 补码均相等。

负数

  • 反码求法：
    1. 符号位不变。
    2. 其他位取反。
  • 补码求法：
    1.符号位不变。
    2.其他位取反。
    3.最后一位加1。

例子

以123和-123为例：

  • [123] 原码：01111011。 反码：01111011。 补码：01111011。
  • [-123]原码：11111011。 反码：10000100。 补码：10000101。

二进制转换成10进制

  1. 如果为正数, 则直接求即可
  2. 如果为负数, 取反+1, 然后求出数值前面加个负号。