位运算

位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

左移<<

1
2
3
如数据：1010<<1
1010左移一位后：10100
即向左移动，低位补0

右移>>

1
2
3
如数据：1010>>1
1010右移一位：101
向右移动

按位与&

1
2
3
4
如：1 0 1 0
  & 1 1 0 0
  ————————————
    1 0 0 0

按位或|

1
2
3
4
如：1 0 1 0
 |  0 1 1 0
 _____________
    1 1 1 0

按位取反

1
2
3
如：~1010
 
取反后：0101

异或^

1
2
3
4
如：  1 0 1 0 0 1
  ^   1 1 0 0 1 0
    _______________
      0 1 1 0 1 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
37
a ∣∼a=−1(按位取反)
    
a & ∼a=0
    
a ∣ (a & b)=a
    
a & (a ∣ b)=a
    
a⊕0=a，a⊕a=0(快速判断数值是否相等：a ⊕ b = = 0 ， 与 a = = b等效)

a & b+a∣b=a+b
    
0 ⊕ 1⊕ 2⊕ (…)⊕ (2^m−1)=0(2≤m)
    
分配律    
a & (b ∣ c)=(a & b) ∣ (a & c)    
a⊕ (b ∣ c)=(a⊕b) ∣ (a⊕c)
结合律与交换律
    (a ∣ b) ∣ c=a ∣ (b ∣ c)
    (a & b) & c=a & (b & c)
    (a⊕b)⊕c=a⊕(b⊕c)
    a ∣ b=b ∣ a
    a & b=b & a
    a⊕b=b⊕a
    
    取反的性质
    ~a+1 = -a 
    
    一些其他操作
    取出整数在二进制的第k位 （n>>k）&1
    取出0-k-1位  n&((1<<k)-1)   //解释一下，就是构造0-k-1位都是1
    把整数n在二进制表示的第k位取反  n⊕(1<<k)
    对整数n在二进制表示下的第k位赋值1  n ∣ (1<<k)
    对整数n在二进制表示下的第k位赋值0  n & (∼(1<<k))
    将x最右边的1置为0(去掉最右边的1) x & (x−1)
    将x最右边的0置为1 x ∣ (x+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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
异或运算交换两个整数  
a = a ∧ b
b = a ∧ b
a = a ∧ b
将x 左移一位实现× 2,将x 右移一位实现÷ 2
a < < 1 ≡ a ∗ 2 
a > > 1 ≡ a / 2   
快速判断x是否是2的幂次
if(x & (x - 1) == 0) return 1;
return 0;
快速判断数值是否相等
if(a ^ b == 0) return 1;
return 0;
统计x二进制表示下1的个数
int count(int x)
{
    int cnt = 0;
    while(x){
        x = x & (x - 1);
        cnt ++;
    }
    return cnt;
}
位运算改变正负性
 int change(int a){
    return ~ a + 1;
}
位运算实现对p取余（p为2^k)
int mod(int a,int p){
    return a & (p - 1);
}
绝对值
int abs(int a){
    return ~(a >> 31) ? a : ~a + 1;
}
一个数组里，所有的数字都出现两次，只有一个数字出现一次，找出这个数字
    while(cin>>n){
            int sum,a;
            for(int i = 0;i<n;i++){
                cin>>a;
                if(i==0)sum = a;
                else sum = sum^a;//所有数字异或起来-〉异或的性质：自己异或自己为0，0异或n = n;
            }
        cout<<sum<<endl;
     }
快速幂
#include<iostream>
using namespace std;
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    int res=1%p;//初始化res，因为是幂积运算，所以初始化为1
    while(b)
    {
        if(b&1)//看b的最后一位是不是1。
            res=res*1ll*a%p;
        a=a*1ll*a%p;
        b>>=1;//对b右移
    }
    cout<<res<<endl;
    return 0;
}
64位整数乘法
a*b可以转化为
a + a + a + a +…+ a（一共b个a相加）
a^b可以转化为
a * a * a * a * … * a（一共b个a相乘）
所以对于a * b也可以采用上题的思想    
#include<iostream>
typedef unsigned long long LL;//考虑到最大单数为1e18，有可能会到达1e19的数量级
//所以开了unsigned long long
using namespace std;
int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    LL res=0;//初始化为0
    while(b)
    {
        if(b&1)//如果b的最后一位是1
            res=(res+a)%p;//进行加和操作
        a=(a+a)%p;
        b=b>>1;//b右移一位
    }
    cout<<res<<endl;
    return 0;
}
lowbit，即a&(-a)，可以取出a的最低位，可以用于树状数组


线性基

我们有n个数，在二进制表示下共有m位，需要构造一组基底，使得这n个数都能由这些基底异或出来。

这个基底就是线性基。

任何数的集合都有线性基。

线性基的三个性质：

1.n个数都可以由线性基中的某些数异或出来。

2.线性基里的数的数量一定是最小的。

3.线性基里的任意一些数异或的结果都不为0。

目前还不太懂，先贴上来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void ins(int x)
{
    for (int i=60;i>=0;i--)
    {
        if (x&(1ll<<i))
        {
            if (f[i]) x^=f[i];
            else
            {
                f[i]=x;
                break;
            }
        }
    }       
}

内建函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
内建函数
GCC 中还有一些用于位运算的内建函数：

int __builtin_ffs(int x) ：返回 x 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 x 为 0 时返回 0 。

int __builtin_clz(unsigned int x) ：返回 x 的二进制的前导 0 的个数。当 x 为 0 时，结果未定义。

int __builtin_ctz(unsigned int x) ：返回 x 的二进制末尾连续 0 的个数。当 x 为 0 时，结果未定义。

int __builtin_clrsb(int x) ：当 x 的符号位为 0 时返回 x 的二进制的前导 0 的个数减一，否则返回 x 的二进制的前导 1 的个数减一。

int __builtin_popcount(unsigned int x) ：返回 x 的二进制中 1 的个数。

int __builtin_parity(unsigned int x) ：判断 x 的二进制中 1 的个数的奇偶性。
    由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。