位运算

本文最后更新于 2024年9月15日 晚上

基础知识回顾：

原码 补/反码
正数 本身 本身
负数 正数原码修改符号位 负数原码除符号位取反 + 1
8 00000000 00000000 00000000 00001000 00000000 00000000 00000000 00001000
-8 10000000 00000000 00000000 00001000 11111111 11111111 11111111 11111000

得到一个相反数，全部取反再+1

异或运算

性质

  • 异或运算是无进位相加（1+1=10，忽略进位，即为无进位相加）
11010
+ 10110
= 01100
  • 异或运算满足交换律、结合律，也就是同一批数字，可以改变异或的顺序，最终的结果都是一样的，因为异或是一种无进位的加法，同理于正常的加法
  • $0 \oplus n = n, n \oplus n = 0, 0 \oplus 0 = 0$
n 11010
+ 00000
= 11010
  • 整体异或和如果是 $x$, 整体中某个部分的异或和如果是 $y$, 那么剩下部分的异或和是 $x \oplus y$
    $a \oplus b = c, a=b \oplus c, b=a \oplus c$

取球问题

规则：
袋子里一共有a个白球，b个黑球
取两球，若为黑+白，放回一个黑球，若为2白或2黑，则重新放入一个白球

白：0 黑：1
取两球为异或运算，可以理解为将两个数拿出来异或后再放回去
所以偶数个1无进位相加为0，奇数个1无进位相加为1

交换两数

交换值，前提是a,b的数值不同，了解即可因为在数组循环等中可能会存在l==r还是执行交换语句。使用这种方法会改变值。

1
2
3
4
5
int a=0;
int b=10;
a=a^b;//a1=a^b
b=a^b;//b1=a^b^b=a
a=a^b;//a2=a^a^b=b

比较大值

不会溢出分析：溢出后c的正负可能会发生改变，因此我们判断大小时的条件只用c不会溢出的情况下判断，无法确定是否溢出时不用c进行判断
即ab符号不同，c不会溢出，ab符号相同，c可能溢出，索引在判断returnA时只有sameAB时才会用c进行判断

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
//必须保证n一定是0或者1
//0变1，1变0
public static int flip(int n){
  return n ^ 1;
}
//非负数返回1负数返回0
public static int sign(int n){
  return flip(n>>>31);//n>>>31,右移31位，使符号位移动到0位置
}
//有溢出风险的实现，c可能超出整数范围
public static int getMax1(int a, int b){
  int c = a - b;
  int returnA = sign(c);//非负数返回1负数返回0
  int returnB = flip(returnA);//非负数返回0负数返回1,与returnA相反
  return a * returnA + b * returnB;
}
//没有任何问题的实现
public static int getMax2(int a, int b){
  int c = a - b;
  int sa = sign(a);
  int sb = sign(b);
  int sc = sign(c);
  int diffAB = sa ^ sb;//判断ab符号是否相同。不同为1，相同为0
  int sameAB = flip(diffAB);//不同为0，相同为1
  int returnA = diffAB * sa + sameAB * sc;//a>b的条件为 ab相同c为非负，ab不同a为非负
  int returnB = flip(returnA);
  return a * returnA + B * returnB;
}

cpp代码实现
c中右移操作符>>，对于有符号数，右移时，符号位不变，左边补符号位，对于无符号数，右移时，左边补0
例如8>>31,则是11111111111111111111，实际值为-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
//c中右移操作符>>，对于有符号数，右移时，符号位不变，左边补符号位，对于无符号数，右移时，左边补0
//例如8>>31,则是11111111111111111111，实际值为-1，并不会只剩下符号位1
int flip(int n)
{
    return n ^ 1; // 必须保证n一定是0或者1，0变1，1变0
}
// 非负数返回1负数返回0
int sign(int n)
{
    return !((n >> 31)&1); // n >> 31, 右移31位，使符号位移动到0位置
}
// 有溢出风险的实现，c可能超出整数范围
int getMax1(int a, int b)
{
    int c1 = a - b;
    int returnA = sign(c1);       // 非负数返回1负数返回0
    int returnB = flip(returnA); // 非负数返回0负数返回1, 与returnA相反
    return a * returnA + b * returnB;
}
// 没有任何问题的实现
// 不会溢出分析：溢出后c的正负可能会发生改变，因此我们判断大小时的条件只用c不会溢出的情况下判断，无法确定是否溢出时不用c进行判断
// 即ab符号不同，c不会溢出，ab符号相同，c可能溢出，索引在判断returnA时只有sameAB时才会用c进行判断
int getMax2(int a, int b)
{
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    int diffAB = sa ^ sb;                    // 判断ab符号是否相同。不同为1，相同为0
    int sameAB = flip(diffAB);               // 不同为0，相同为1
    int returnA = diffAB * sa + sameAB * sc; // a>b的条件为 ab相同c为非负，ab不同a为非负。
    int returnB = flip(returnA);
    return a * returnA + b * returnB;
}

找出缺失的数值

长度为n的数组，里面有0~n-1的数，现在有一个缺失的值

总异或和=出现的异或和$\oplus$缺失值
缺失值=总异或和$\oplus$出现的异或和

1
2
3
4
5
6
7
8
9
public static int missingNumber(int[] nums){
  int eorall = 0,eorhas = 0;
  for (int i = 0; i < nums.length; i++){
    eorall ^= i;
    eorhas ^=nums[i];
  }
  eorall ^=nums.length;
  return eorall ^ eorhas;
}

找出出现奇数次的值

数组中1种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数
依次异或过去，出现两次的数异或为0，只剩下那一个数

1
2
3
4
5
6
7
public static int singleNumber(int[] nums){
  int eor = 0;
  for(int num : nums){
    eor ^= num;
  }
  return eor;
}

返回两个奇数次数

数组中有2种数出现了奇数次，其他的数都出现了偶数次，返回这两种出现了奇数次的数

Brian Kernighan算法 - 一个数&它的相反数可以得到二进制状态中最右侧的1为1，其他为0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] singNumber(int[] nums){
  int eor1 = 0;
  for (int num : nums){
    eor1 ^= num;
  }
  //eor1=a^b,a!=b，则eor至少有一位是1
  int rightOne = eor1 & (-eor1);//最右侧的1位1为1，其他为0
  int eor2 = 0;
  for (int num : nums){
    if((num & rightOne) == 0){//找出eor最右侧1位置为0的数，全部异或和必为其中一个数
      eor2 ^= num;
    }
  }
  return new int[] { eor2, eor1 ^ eor2};
}

返回多个数

数组中只有1种数出现次数少于m次，其他数都出现了m次，返回出现次数小于m次的那种数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int find(int[] arr, int m){
  int[] cnts = new int[32];
  for (int num : arr){
    for (int i = 0; i < 32; i++){
      cnts[i] +=(num >> i) & 1;
    }
  }
  int ans = 0;
  for (int i = 0; i < 32; i++){
    if (cnts[i] % m != 0){
      ans ^= 1 << i;
    }
  }
  return ans;
}

位运算

判断整数是否为2的幂

    2的幂次在二进制中只有一个1，所以我们可以通过Brian Kernighan算法得到最右侧为1的数与原数比较是否相同

1
2
3
public static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

判断整数是否为3的幂

1
2
3
public static boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467%n == 0;//1162261467是int范围内最大的3的幂
}

求解大于等于n的最小的2次幂

1
2
3
4
5
6
7
8
9
10
11
12
public static  final int near2power(int n){
    if (n == 0) {
        return 1;
    }
    n--;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;//这里是32位系统，如果是64位系统，就是直到n |= n >>> 32;该实现的是将最左边的1后面的所有位都置为1
    return n + 1;
}

代码详细例子理解

区间[left，right]内所有数字&的结果

逆序二进制状态

二进制中有几个1

note > 408 > 数据结构与算法
#算法
位运算
http://2819461143wp.github.io/位运算/
作者
cwdp.sky
发布于
2024年9月9日
许可协议