位运算的应用

判断奇偶#

奇数的二进制最低位一定是1, 而偶数的二进制最低位一定是0, 所以有

1
2
3
if((1 & num) == 1) // num 为奇数
    
if((1 & num) == 0) // num 为偶数

乘2除以2#

1
2
3
4
5
6
7
num >> 1 == num / 2
    
num << 1 == num * 2
    
1 << n == Math.pow(2, n)

移除最低位的1#

比如num的二进制为0000 1010, 移除最低位的1后变成 0000 0100

1
int res = num & (num - 1);

相关题:

获取最低位的1#

比如num的二进制为0000 1010, 获取最低位的1的值应该是 0000 0010, 即只保存最低位的1, 移除其他所有1

1
int res = num & (-num);

寻找唯一#

当一个数组中, 除了一个数只出现了一次, 其余都出现了两次, 找到这个数

^具有复原的特性, 且满足交换律, 当同一个数异或两次, 就会回到原来的状态, 即 n^m^m == n,

还有0^m == m, m^m == 0

1
2
3
4
5
6
7
8
9
10
// 对于任意三个数 m,n,s 一定满足以下关系
m ^ n == s;
m ^ s == n;
s ^ n == m;
m ^ n ^ s == 0;

n ^ m ^ m == n;

0 ^ m == m;
m ^ m == 0;

奇数位的1#

十六进制数0x5555 5555 其二进制为=> 0101 0101 0101 0101 0101 0101 0101 0101, 发现是奇数位上都是1

1
2
if((num & (num -1) == 0))  // num是2的次幂数 
	if(num & 0x55555555 == num)  // num是4的次幂数

获取最高位的1所在位#

比如 0001 0011 最高位的1在第五位, 返回5

1
2
3
      int n = 0, m = 1;
      while(m <= num && ++n > 0) m <== 1;
// (n-1)即是位数

第i位的数#

(n >> i) & 1可以表示n的二进制倒数第i位是1还是0，

异或^的性质#

image-20230602150909806

第五点:

1
2
3
4
5
1 ^ 2 ^ 3 == 0   一定成立

4 ^ 5 ^ 6 ^ 7 == 0 一定成立

4i ^ (4i + 1) ^ (4i + 2) ^ (4i + 3) == 0