高逼格的位运算小结-蒲公英云

高逼格的位运算小结

た入场券 2022-01-27 15:09 329阅读 0赞

位算法的效率有多高这里就不讲了，位运算其实有很多技巧，比如判断是否是2的幂次方、判断奇偶性、交换两个数、找出不重复的数、找出不大于N的最大的2的幂指数，掌握这些可以装逼。

位与

两位数同时为“1”，结果才为“1”，否则为0

0&0=0;

0&1=0;

1&0=0;

1&1=1;

位或

两位数只要有一个为1，其值为1

0|0=0；

0|1=1；

1|0=1；

1|1=1；

异或

两位数只能有一个1则为1，否则为0

0^0=0；

0^1=1；

1^0=1；

1^1=0

左移

二进制位全部左移若干位（左边的二进制位丢弃，右边补0）

1<<1=2;
1<<2=4;
1<<3=8

右移

二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃

32>>1=16;
32>>2=8;
32>>3=4;

实例

简写

a &=b //相当于a=a& b
a |=b //相当于a=a |b
a >>=b //相当于a=a>> b
a <<=b //相当于a=a<< b
a ^= b //相当于a=a^ b

有A（>=0）、B（2的平方n，n>=0）
A * B == A << n
A / B == A >> n
A%B == A&(B-1)

判断是否是2的幂次方

(number & number - 1) == 0

判断奇偶性

奇书(最后一位为1）：n & 1 == 1

偶数(最后一位为0）：n & 1 == 0

交换两个数

int tmp = x;
x = y;
y = tmp;

等价于：
x = x ^ y
y = x ^ y
x = x ^ y

找出不重复的数

有一组整型数据有一个数只出现了一次，其他的数都出现了两次，找出这个不重复的。

一般人想到的是哈希表来存储，而采用位运算来做，时间复杂度为 O(n)，空间复杂度为 O(1)，绝对高逼格。两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身。

比如：1， 2， 3， 4， 5， 1， 2， 3， 4

1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5

找出不大于N的最大的2的幂指数

一般人想到的就是让 1 不断着乘以 2，时间复杂度是 O(logn)，那如果改成位运算时间复杂度近似 O(1)，高逼格吧。

例如 N = 19，那么转换成二进制就是 00010011，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000=16，如何做呢？

//传统的做法就是让 1 不断着乘以 2
int findN(int N){
   int sum = 1;
   while(true){
        if(sum * 2 > N){
            return sum;
        }
        sum = sum * 2;
   }
}
//1.找到最左边的 1，然后把它右边的所有0变成1
//2.把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000
//3.把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000
int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}