玩转位运算的N条实践小技巧

约定不等于承诺〃 2023-07-18 14:21 1阅读 0赞

## 写在前面 ##

**如果觉得本篇文章有所帮助，记得点个关注和点个赞哦，非常感谢支持。**  
对于位运算我们应该不陌生（当然，如果你还很陌生，你可以看我之前写过的[关于位运算的文章][Link 1]，挺详细的），这一篇主要是针对平时我们日常生活中，碰到的关于位运算的一些问题，而总结出来的一些实践技巧，能够帮助我们快速解决一下相关问题，有助于玩转位运算的操作。本文会不断更新，日后碰到很多奇思妙想会继续更新进来，也欢迎大家留言更新。

## N条实践技巧 ##

*  **在位运算中，我们如果想要将二进制位中最右边的1置为0，我们只需要`n & (n-1)`**

这一点其实不难理解，我们知道，在二进制中，`n - 1` 会导致 `n` 最右边的 `1` 要退 `1` ，就像我们在十进制中满十进一，少十退一。然后此时用 `n & (n-1)` 进行运算，就可以成功的去掉最右边的 `1`

*  **在位运算中，我们如果想要取二进制位中最右边的1，我们只需要`n & (-n)`**
 *  **计算一个整数二进制中1的个数**  
    因为1可以不断的通过 `x&(x-1)` 这个操作消去，所以当最后的值变成 `0` 的时候，也就求出了二进制中 `1` 的个数
 *  **如果将整数A转换成整数B,需要改变多少个比特位**  
    思考将整数 `A` 转换为 `B`，如果 `A` 和 `B` 在第`i`（`0<=i<32`）个位上相等，则不需要改变这个BIT位，如果在第 `i` 位上不相等，则需要改变这个BIT位。所以问题转化为了A和B有多少个BIT位不相同。联想到位运算有一个异或操作，相同为 `0`，相异为 `1`，所以问题转变成了计算A异或B之后这个数中 `1` 的个数
 *  **去考虑这样一个问题，一个数大于一个数意味着什么？或者说，怎么判断一个数大于一个数？**

不管在十进制还是二进制，都存在这样一个事实 ，我们只需要从高位向低位看去，直到某一位不相同，大小也就判断了出来。十进制中，比如 `6489...` 和 `6486...`，由于 `9 > 6`，所以不管后边的位是什么 `6489...` 一定会大于 `6486...` 。对于二进制，一样的道理，但因为二进制只有两个数 `0` 和 `1`，所以当出现某一位大于另一位的时候，一定是 `1 > 0`。更形象一点如下，

m -> S S S 0 X X X X
    n -> S S S 1 X X X X

前边的若干位都相同，然后从某一位开始从 `0` 变成 `1`。通过这个认识，我们有时候可以配合移位操作，完成许多的巧妙思路。

*  **判断该数是不是二的次方数，我们只需要对 `(n & (n - 1))` 进行运算，如果结果为0，那么就是二的次方数**
 *  **判断一个数的奇偶性，我们只需要对 `i & 1` 进行运算，如果结果为 `1` 则为偶数，反之否则为奇数**
 *  **两个相同的数进行异或(^)为0**

我们可以利用异或的这个特性来消除重复的数, 例如找出一个数组中落单的数(数量为奇数的某个数), 相反我们也可以利用这个特性来找出数组中唯一成对的数。

*  **利用异或实现数的交换**

a = a ^ b;
    b = a ^ b;
    a = a ^ b;

*  **利用位移实现乘/除2的幂次倍，即一个数向右移1位就相当于除以2, 右移2位相当于除以4，向左移就是乘法，规律同除。**

int a = 3>>1; // a =1,注意此除法是整除, 不保留小数位
    int a = 3<<1; // a = 6
    int a = 3<<2; // a = 12

*  **对2的n次方取余，可以使用 `m & (n - 1)` 运算，因为，如果是 `2` 的幂，`n` 一定是`000100...`，n-1就是 `000011....` ，所以做与运算结果保留m在n范围的非0的位**
 *  **我们可以通过 `~n + 1` 来获得 `n` 的相反数，当然，也可以写成这样 `(n ^ -1) + 1`**
 *  **如果碰到 `if(x == a) x = b` 或者 `if(x == b) x = a` 可以通过以下这样代替 `x = a ^ b ^ x`**
 *  **n倍数补全，当 `n` 为 `2` 的幂时，`(x + n - 1) & ~(n - 1)` 会找到第一个大于 `x` 的数，且它正好是 `n` 的整数倍。**
 *  **计算 `n+1` 与 `n-1` ，`-~n == n + 1`，`~n`为其取反，负号 ’ - ’ 再对其取反并加 `1`。`~-n == n - 1`，思路就是找到最低位的第一个 `1`，对其取反并把该位后的所有位也取反，即`01001000`变为`01000111`。**
 *  **判断二进制中1的奇偶性**

x = x ^ (x >> 1);
    x = x ^ (x >> 2);
    x = x ^ (x >> 4);
    x = x ^ (x >> 8);
    x = x ^ (x >> 16);
    
    cout << (x & 1) << endl; // 输出 1 为奇数

以十进制数1314520为例，其二进制为0001 0100 0000 1110 1101 1000。第一次异或操作的结果如下：

0001 0100 0000 1110 1101 1000
    ^ 0000 1010 0000 0111 0110 1100
    = 0001 1110 0000 1001 1011 0100

得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：

0001 1110 0000 1001 1011 0100
    ^ 0000 0111 1000 0010 0110 1101
    = 0001 1001 1000 1011 1101 1001

结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。

一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里1的奇偶性。

*  **取出最右侧的1**

int quyu(int pos){ 
        return pos & (~pos + 1);
    }

## 表格 ##

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>示例</th> 
   <th>位运算</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>去掉最后一位</td> 
   <td>(101101-&gt;10110)</td> 
   <td>x &gt;&gt; 1</td> 
  </tr> 
  <tr> 
   <td>在最后加一个0</td> 
   <td>(101101-&gt;1011010)</td> 
   <td>x &lt;&lt; 1</td> 
  </tr> 
  <tr> 
   <td>在最后加一个1</td> 
   <td>(101101-&gt;1011011)</td> 
   <td>x &lt;&lt; 1+1</td> 
  </tr> 
  <tr> 
   <td>把最后一位变成1</td> 
   <td>(101100-&gt;101101)</td> 
   <td>x | 1</td> 
  </tr> 
  <tr> 
   <td>把最后一位变成0</td> 
   <td>(101101-&gt;101100)</td> 
   <td>x | 1-1</td> 
  </tr> 
  <tr> 
   <td>最后一位取反</td> 
   <td>(101101-&gt;101100)</td> 
   <td>x ^ 1</td> 
  </tr> 
  <tr> 
   <td>把右数第k位变成1</td> 
   <td>(101001-&gt;101101,k=3)</td> 
   <td>x</td> 
  </tr> 
  <tr> 
   <td>把右数第k位变成0</td> 
   <td>(101101-&gt;101001,k=3)</td> 
   <td>x &amp; ~(1 &lt;&lt; (k-1))</td> 
  </tr> 
  <tr> 
   <td>右数第k位取反</td> 
   <td>(101001-&gt;101101,k=3)</td> 
   <td>x ^ (1 &lt;&lt; (k-1))</td> 
  </tr> 
  <tr> 
   <td>取末三位</td> 
   <td>(1101101-&gt;101)</td> 
   <td>x &amp; 7</td> 
  </tr> 
  <tr> 
   <td>取末k位</td> 
   <td>(1101101-&gt;1101,k=5)</td> 
   <td>x &amp; (1 &lt;&lt; k-1)</td> 
  </tr> 
  <tr> 
   <td>取右数第k位</td> 
   <td>(1101101-&gt;1,k=4)</td> 
   <td>x &gt;&gt; (k-1) &amp; 1</td> 
  </tr> 
  <tr> 
   <td>把末k位变成1</td> 
   <td>(101001-&gt;101111,k=4)</td> 
   <td>x | (1 &lt;&lt; k-1)</td> 
  </tr> 
  <tr> 
   <td>末k位取反</td> 
   <td>(101001-&gt;100110,k=4)</td> 
   <td>x ^ (1 &lt;&lt; k-1)</td> 
  </tr> 
  <tr> 
   <td>把右边连续的1变成0</td> 
   <td>(100101111-&gt;100100000)</td> 
   <td>x &amp; (x+1)</td> 
  </tr> 
  <tr> 
   <td>把右起第一个0变成1</td> 
   <td>(100101111-&gt;100111111)</td> 
   <td>x | (x+1)</td> 
  </tr> 
  <tr> 
   <td>把右边连续的0变成1</td> 
   <td>(11011000-&gt;11011111)</td> 
   <td>x | (x-1)</td> 
  </tr> 
  <tr> 
   <td>取右边连续的1</td> 
   <td>(100101111-&gt;1111)</td> 
   <td>(x ^ (x+1)) &gt;&gt; 1</td> 
  </tr> 
  <tr> 
   <td>去掉右起第一个1的左边</td> 
   <td>(100101000-&gt;1000)</td> 
   <td>x ^ (x ^ (x-1))</td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: https://dengbocong.blog.csdn.net/article/details/103668004