红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【数学】位运算

发表于 分类于 ，
本文字数： 6.2k 阅读时长 ≈ 11 分钟
介绍了位运算的基础知识与一些实际操作

位运算

按位与、或与异或

这三种运算都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

性质

  • 交换律：A&B=B&A, A^B=B^A

  • 结合律：(A&B)&C=A&(B&C) (同符号即可)

  • 等幂律：A&A=A，A∣A=A

  • 零律：A&0=0

  • 同一律：A∣0=A，A^0=A，A^B^B=A

  • 异或的本质是无进位相加

  • 异或满足交换结合律

  • 异或的自反性：\(a\oplus b\oplus b = a\)

  • 与0相关

    • 任何数与0异或结果为原数：\(0 \oplus n=n\)

    • 任何数和自己异或结果为0：\(n\oplus n=0\)

    • 整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和为x^y:

      即\(a\oplus b=c \Rightarrow a=c\oplus b, b=c \oplus a\)

取反

取反是对一个数的运算，即单目运算

它的作用是将一个数的二进制补码中的0和1取反变为1和0

e.g. ~5(00000101) = -6(11111010)

注意：有符号整数的符号位也会取反

e.g. ~-5(11111011) = 4(00000100)

左移与右移

  • 左移：num << i 表示将 num 的二进制表示向左移动 i 位所得的值。

左移时，左端多出的bits丢弃，右端用0填充

  • 右移：num >> i 表示将 num 的二进制表示向右移动 i 位所得的值。

右移时，右端多出的bits丢弃，对于左端有两种方法：

  • 逻辑移动：左端用0填充

  • 算术移动：左端用最高有效位的值填充（默认使用该方法）

（>>表示算术右移，>>>表示逻辑右移）

  • 注意移位时的未定义行为：

    • 移位数出现负值(a<<-1)

    • 移位数大于左值的位数(a<<32)

应用

操作一个数的二进制位

(以下提到的位数下标为0)

  • 获取数a的第b位：(a >> b) & 1

  • 将数a的第b位设为0：a & ~(1 << b)

  • 将数a的第b位设为1：a | (1 << b)

  • 将数a的第b位取反：a ^ (1 << b)

  • 取数a的末k位：a & (1 << a)

  • 把数a的末k位变为1：a | (1 << k)

  • 把数a的末k位取反：a ^ (1 << k)

  • 把数a的右边连续的1变为0：a & (a+1)

  • 把数a的右边第一个1变为0：a & (a-1)

  • 把数a的右边连续的0变为1：a | (a-1)

  • 把数a的右边第一个0变为1：a | (a+1)

  • 取数a右边连续的1：(a ^ (a+1)) >> 1

  • 取数a最低位的1（lowbit）：a & (-a)

  • 统计二进制数1的个数：

1
2
3
4
5
6
7
8
9
// 统计二进制数1的个数
int count(int x){
    int cnt = 0;
    while(x){
        x = x & (x - 1);
        cnt ++;
    }
    return cnt;
}

关于2的幂次的操作

  • 将一个数乘/除2的非负整数次幂

    • n<<m等价于\(n×2^m\)

    • n>>m等价于$ $

  • 判断一个整数是不是2的幂：n>0 && (x&(x-1))==0

  • 判断一个整数是不是3的幂：n>0 && 1162261467%n==0

  • 返回大于等于n的最小的2的幂：

1
2
3
4
5
6
7
8
9
10
11
// 找到大于等于最近的二次幂数
int nearsquare(int n){
  if (n<=0) return 1;
  n--;
  n|=n>>1;
  n|=n>>2;
  n|=n>>4;
  n|=n>>8;
  n|=n>>16;
  return n+1;
}

其他骚操作

交换两个数的值

1
2
3
4
5
6
7
// 交换两个数的值
int a = 1;
int b = 2;
a = a^b;
b = a^b;
a = a^b;
cout << a <<" "<< b <<endl;

应满足a要与b有不同的内存空间

返回两个数的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 反转1与0
int flip(int n){
  return (n^1);
}
// 获取二进制符号位，非负数返回1，负数返回0
int sign(int n){
  return flip(n>>31);
}
// 返回两个数的最大值
  a = 1;
  b = 2;
  int c = a-b;
  int sa = sign(a);
  int sb = sign(b);
  int sc = sign(c);
  int diff = (sa^sb); // 判断a与b符号是否不同，不同为1
  int same = flip(diff); // 判断a与b符号是否相同，相同为1
  // return a的条件：ab符号不同且a非负，ab符号相同且c非负
  int returna = diff*sa+same*sc;
  int returnb = flip(returna);
  cout<<a*returna+b*returnb<<endl;

找到缺失的数字

将不缺时的所有数字异或和与缺时的所有数字异或和求异或，得到的即为缺失的数字

1
2
3
4
5
6
7
8
9
10
// 找到缺失的数字
 int all = 0;
 int has = 0;
 int nums[]={0,1,2,3,4,5,6,7,8,0};
 int length = 10;
 for (int i = 0;i<length;i++){
   all ^=i;
   has ^=nums[i];
 }
 cout<< (all^has) << endl;

找唯一出现奇数次的数

使用eor变量存储异或，将所有数异或入eor，最后eor即为唯一出现奇数次的数

因为\(n\oplus n=0\)

1
2
3
4
5
6
7
// 找唯一出现奇数次的数：
int eor = 0;
int num2[]={1,1,2,2,3,3,3};
for (int i = 0; i<7;i++){
  eor^=num2[i];
}
cout << eor<<endl;

找唯二出现奇数次的数

若a与b出现了奇数次，我们计算数组中所有数的异或（此时出现偶数次的数都变成了0），用eor1记录，并取结果的lowbit

取eor2变量，只对数组中上面求出位置不为1的数求异或

则此时a与b根据该位置是否为1分到了eor1与eor2两个部分

故eor2为其中一个，eor1^eor2为另一个

1
2
3
4
5
6
7
8
9
10
11
12
// 找唯二出现奇数次的数：
vector<int> nums;
int eor1 = 0;
for (auto num:nums){
  eor1 ^=num;
}
int right = eor1&(-eor1);
int eor2 = 0;
for (auto num:nums){
  if((num&right)==0)eor2^num;
}
cout << eor2 <<' '<<(eor1^eor2);

找唯一出现次数小于m次的数

若有一个数不够m次，则二进制每一位的1的数量不为m的整数倍

求出每位模完的余数，若余数为0则在该位为0，否则为1

记录可以使用一个长32的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 找唯一出现小于m次的数
int arr[]={1,1,2,2,3};
int cnts[32];
int m = 2;
for (int i = 0;i<5;i++){
  for (int j = 0; j<32;j++){
    cnts[j]+= (i>>j)&1;
  }
}
int ans = 0;
for (int i = 0; i<32;i++){
  if (cnts[i]%m!=0){
    ans|=1<<i; // 将1左移i为并或到结果中
  }
}
cout << ans<<endl;

判断整数是不是2的幂

2的幂次的二进制只有一个1

我们用lowbit取出二进制最右侧的1，此时若与n相等，则n为2的幂

即满足n>0&&n==(n&-n)或n>0&&(x&(x-1))==0即为2的幂

判断整数是不是3的幂

如果某个数字是3的幂次，则该数一定含有3这个质数因子

1162261467是int类型范围内最大的3的幂(\(3^{19}\))

该数只含有3这个质数因子，若n也只含有3这个质数因子，则让该数被上面的数模，若为0则是3的某次幂

即满足return (n>0 && 1162261467%n==0)

返回大于等于n的最小的2的幂

n<=0时，结果均为1

n>0时，让n–，让最左边的1右移一位（避免n刚好是2的幂的情况）

然后将后面的0通过右移与或运算全部刷为1（n为2的幂的时候，右边已经变为全1），得到的结果+1即为结果

1
2
3
4
5
6
7
8
9
10
int nearsquare(int n){
  if (n<=0) return 1;
  n--;
  n|=n>>1;
  n|=n>>2;
  n|=n>>4;
  n|=n>>8;
  n|=n>>16;
  return n+1;
}

求区间所有数的与

每次减掉right的二进制最右侧的1，如果仍大于left，证明最右侧仍存在不能留下的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
int alland(int l, int r){
  while(r>l){
    r-=(r&-r);
  }
  return r;
}
```

### 逆序二进制的状态

首先每两位内部互相交换，然后交换后的每四位内部两位两位的交换，依次类推

如：

abcdefgh -> ba dc fe hg 

ba dc fe hg -> dc ba  hg fe

dc ba  hg fe -> hg fe dc ba

 故我们可以采取如下逻辑进行交换：

abcdefgh与10101010(aa)或运算，得到a0c0e0g0

abcdefgh与01010101(55)或运算，得到0b0d0f0h

然后将a0c0e0g0右移一位得到0a0c0e0g，0b0d0f0h左移一位得到b0d0f0h0

两者进行或运算，得到badcfehg

同理，第二次用11001100(cc)，00110011(33)进行运算，左移右移两位，再进行或运算

第三次用 11110000(f0)，00001111(0f )进行运算，左移右移四位，再进行或运算

第四次用1111111100000000(ff00)，0000000011111111(00ff)进行运算，左移右移八位，再进行或运算

```C++
// 反转二进制
int reversebits(int n){
  n = ((n&0xaaaaaaaa)>>1)|((n&0x55555555)<<1);
  n = ((n&0xcccccccc)>>2)|((n&0x33333333)<<2);
  n = ((n&0xf0f0f0f0)>>4)|((n&0x0f0f0f0f)<<4);
  n = ((n&0xff00ff00)>>8)|((n&0x00ff00ff)<<8);
  n = (n>>16)|(n<<16);
  return n;
}
```



## 位运算表示算术运算

- 加法：`a+b = a^b+(a&b)<<1`

- 减法：转换为补码

  `a-b = a+(-b)=a+(~b+1)`

- 乘法：相当于一个数的每一位乘以另一个数的所有位次然后左移相应位数加到答案上

  ```c++
  int mul(int a, int b) {
      int absA = a < 0 ? add(~a, 1) : a;
      int absB = b < 0 ? add(~b, 1) : b;
      if (absA < absB) swap(absA, absB); // 减小循环次数
      int res = 0;
      while (absB) {
          if ((absB & 1) != 0)
              res = add(res, absA);
          absA <<= 1;
          absB >>= 1;
      }
      if ((a & 0x80000000) != (b & 0x80000000)) res = add(~res, 1);
      return res;
  }

  • 除法：a/b=c可以转化为a=b*c，故可以转化为\(a=\sum b\times2^i\)，则c的二进制一定是对应的二进制表示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int div(int a, int b) {
    int absA = a < 0 ? add(~a, 1) : a;
    int absB = b < 0 ? add(~b, 1) : b;
    int res = 0;
    for (int i = 31; i >= 0; i = sub(i, 1) ) {
        if ((absA >> i) >= absB) {
            res |= (1 << i);
            absA = sub(absA, absB << i);
        }
    }
    if ((a & 0x80000000) != (b & 0x80000000)) res = add(~res, 1);
    return res;
}

  • 逐位取反：

    对于任意k与\(0\le x<2^k\)，有\(x\&(2^k-x-1)=0\)，其中\((2^k-x-1)\)等价于给x的逐位取反

内建函数

__builtin系列函数是gcc编译器内置的函数，用于操作二进制位

他们的时间复杂度都是O(1)，在对应函数后加ll即可支持ull的数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// __builtin系列函数是gcc编译器内置的函数，可以带来性能优化
// 注：在对应函数后加ll即可支持ull的数据类型
// 注注：他们的时间复杂度都是O(1)
int x = 64;
// 返回x二进制末尾最后一个1的位置， 下标从1开始，若传入0则返回0
cout << __builtin_ffsll(x)<<endl;
// 返回x从最高位开始的前0数量。若传入0 返回未定义
cout << __builtin_clzll(x)<<endl;
// 返回x从最低位开始连续的0个数。若传入0则返回未定义。
cout << __builtin_ctzll(x)<<endl;
// 返回x中1的出现次数。
cout << __builtin_popcount(x)<<endl;
// 返回x 中 1 的出现次数的奇偶，等价于 __builtin_popcount(x)&1，但比它快。
cout << __builtin_parity(x)<<endl;
// 当x的符号位为0时返回x二进制前导0个数-1，否则返回二进制前导1
cout << __builtin_clrsb(x)<<endl;

//应用
int y = 64;
// 求一个数以2为底的对数,相当于该数二进制位数-1
cout << 31-__builtin_clz(y)<<endl;