高逼格的位运算小结

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

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

<table> 
 <tbody> 
 <tr> 
 <td style="width:69px;"> 位与 &amp; </td> 
 <td style="width:441px;">两位数同时为“1”，结果才为“1”，否则为0</td> 
 <td style="width:193px;"> 0&amp;0=0; &nbsp; 0&amp;1=0; &nbsp; 1&amp;0=0; &nbsp; &nbsp; 1&amp;1=1; </td> 
 </tr> 
 <tr> 
 <td style="width:69px;"> 位或 | </td> 
 <td style="width:441px;">两位数只要有一个为1，其值为1</td> 
 <td style="width:193px;"> 0|0=0； 0|1=1； &nbsp; 1|0=1； &nbsp; 1|1=1； </td> 
 </tr> 
 <tr> 
 <td style="width:69px;"> 异或 ^ </td> 
 <td style="width:441px;">两位数只能有一个1则为1，否则为0</td> 
 <td style="width:193px;"> 0^0=0； 0^1=1； &nbsp; 1^0=1； &nbsp; 1^1=0 </td> 
 </tr> 
 <tr> 
 <td style="width:69px;"> 左移 &lt;&lt; </td> 
 <td style="width:441px;">二进制位全部左移若干位（左边的二进制位丢弃，右边补0）</td> 
 <td style="width:193px;">1&lt;&lt;1=2; 1&lt;&lt;2=4; 1&lt;&lt;3=8</td> 
 </tr> 
 <tr> 
 <td style="width:69px;"> 右移 &gt;&gt; </td> 
 <td style="width:441px;">二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃</td> 
 <td style="width:193px;">32&gt;&gt;1=16; 32&gt;&gt;2=8; 32&gt;&gt;3=4;</td> 
 </tr> 
 </tbody> 
</table>

实例

> 简写
> 
> a &=b       //相当于a=a& b 
> a |=b        //相当于a=a |b 
> a >>=b     //相当于a=a>> b 
> a <<=b     //相当于a=a< 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;
    }

位运算即是在位级别进行操作的技术，它能够帮助我们得到更快地运算速度与更小的内存使用。![24126251][]

[24126251]: /images/20220127/c70c5058baff493caaa35f00a0071281.png