算法刷题：位运算

谁践踏了优雅 2023-09-28 05:11 73阅读 0赞

# 位运算 #

*  程序中的所有数在计算机内存中都是以 0、1 二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。
 *  计算机对二进制数据进行的运算(+、-、\*、/)都是叫位运算，即将符号位共同参与运算的运算

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th>描述</th> 
   <th>运算规则</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>&amp;</td> 
   <td>与</td> 
   <td>两个位都为1时，结果才为1</td> 
  </tr> 
  <tr> 
   <td>I</td> 
   <td>或</td> 
   <td>两个位都为0时，结果才为0</td> 
  </tr> 
  <tr> 
   <td>^</td> 
   <td>异或</td> 
   <td>两个位相同为0，相异为1</td> 
  </tr> 
  <tr> 
   <td>~</td> 
   <td>取反</td> 
   <td>0变1，1变0</td> 
  </tr> 
  <tr> 
   <td>&lt;&lt;</td> 
   <td>左移</td> 
   <td>各二进位全部左移若干位，高位丢弃，低位补0</td> 
  </tr> 
  <tr> 
   <td>&gt;&gt;</td> 
   <td>右移</td> 
   <td>各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）</td> 
  </tr> 
 </tbody> 
</table>

详细可阅：[位运算讲解][Link 1]

--------------------

<table> 
 <thead> 
  <tr> 
   <th>题目一览</th> 
   <th>难度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="https://leetcode.cn/problems/swap-numbers-lcci/" rel="nofollow">面试题 16.01. 交换数字</a></td> 
   <td>★☆☆☆☆</td> 
  </tr> 
  <tr> 
   <td><a href="https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/" rel="nofollow">1342. 将数字变成 0 的操作次数</a></td> 
   <td>★☆☆☆☆</td> 
  </tr> 
  <tr> 
   <td><a href="https://leetcode.cn/problems/number-complement/" rel="nofollow">476. 数字的补数</a></td> 
   <td>★☆☆☆☆</td> 
  </tr> 
  <tr> 
   <td><a href="https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/" rel="nofollow">2044. 统计按位或能得到最大值的子集数目</a></td> 
   <td>★★☆☆☆</td> 
  </tr> 
 </tbody> 
</table>

### 文章目录 ###

*  位运算
 *  【01】 面试题 16.01. 交换数字
 *  【02】 1342. 将数字变成 0 的操作次数
 *  【03】 476. 数字的补数
 *  【04】 2044. 统计按位或能得到最大值的子集数目

--------------------

# 【01】 面试题 16.01. 交换数字 #

![在这里插入图片描述][9da49f9b60c94b6bbc2280ad45b50142.png]  
（1）a\[1\]=( a\[0\] ^ a\[1\] ) ^ a\[1\] —> a\[0\];  
（2）a\[0\] = a\[0\] ^ a\[1\] ^ a\[1\] —> a\[1\];

class Solution {
        
    public:
        vector<int> swapNumbers(vector<int>& a) {
        
                a[0]=a[0]^a[1];  
                a[1]=a[0]^a[1];  //a[1]=(a[0]^a[1])^a[1] -> a[0];
                a[0]=a[0]^a[1];  //a[0]=a[0]^a[1]^a[1] -> a[1];
                return a;
        }
    };

--------------------

# 【02】 1342. 将数字变成 0 的操作次数 #

![在这里插入图片描述][da717d998cf24e9abcc32b341d49ad90.png]

class Solution {
        
    public:
        int numberOfSteps(int num) {
        
            if(num == 0){
        
                return 0;
            }
            if(num & 1){
        
                return numberOfSteps(num - 1) + 1;
            }
            return numberOfSteps(num / 2) + 1;
        }
    };

--------------------

# 【03】 476. 数字的补数 #

![在这里插入图片描述][7718d8751ff8494eb3b9f787fd3b0876.png]  
（1）首先找到最小的一个2的幂k，满足k ≥ num;  
（2）如果num和k相等，说明num是一个2的幂，则二进制表示为1跟上若干个0，那么它的取反就是0跟上若干个1，也就是k - 1 ;  
（3）否则，用k - 1减去num，就得到了对应的相反值（可以自行模拟就明白）；

class Solution {
        
    public:
        int findComplement(int num) {
        
            unsigned int k = 1;
            while(num > k){
             //num=1001
                k <<= 1;        //    10000
            }
            if(num == k){
        
                return k - 1;   
            }                   
            return k-1-num;     //    1111
                                //   -1001
                                //    0110
        }
    
    };

--------------------

# 【04】 2044. 统计按位或能得到最大值的子集数目 #

![在这里插入图片描述][8746e494b8af4ff29475754e0c8502ae.png]  
（1）数字的范围最多还只有16，所以子集的数目最多2的16次；  
（2）每个子集就是这个数 取或者不取，所以正好对应了一个二进制数，二进制上为1代表取，为0代表不取；  
（3）枚举所有可能的子集，计算自己的位或值，然后取最大的那个，等于相同的最大值，则计数器累加，最后返回计数器即可；

class Solution {
        
    public:
        int countMaxOrSubsets(vector<int>& nums) {
        
            int i,j;
            int n=nums.size();
            int maxv=-1,maxc=0;
            for(i=0;i<(1<<n);++i){
        
                    int ans=0;
                    for(j=0;j<n;++j){
        
                        if(i&(1<<j)){
        
                            ans|=nums[j];
                        }
                    }
                    if(ans>maxv){
        
                        maxv=ans;
                        maxc=1;
                    }else if(ans==maxv){
        
                        maxc ++;
                    }
            }
            return maxc;
        }
    };

--------------------

[Link 1]: https://www.runoob.com/w3cnote/bit-operation.html
[9da49f9b60c94b6bbc2280ad45b50142.png]: https://img-blog.csdnimg.cn/9da49f9b60c94b6bbc2280ad45b50142.png
[da717d998cf24e9abcc32b341d49ad90.png]: https://img-blog.csdnimg.cn/da717d998cf24e9abcc32b341d49ad90.png
[7718d8751ff8494eb3b9f787fd3b0876.png]: https://img-blog.csdnimg.cn/7718d8751ff8494eb3b9f787fd3b0876.png
[8746e494b8af4ff29475754e0c8502ae.png]: https://img-blog.csdnimg.cn/8746e494b8af4ff29475754e0c8502ae.png