位运算

末蓝、 2022-07-03 14:26 343阅读 0赞

## 基础知识 ##

位运算是把数字用二进制表示之后，对每一位上0或1的运算。位运算总共只有5种运算：与、或、异或、左移和右移。对于异或操作，需要注意一下`0^0=0; 1^1=0; 1^0=1`。

## 应用：二进制中1的个数 ##

**题目**：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1.因此如果输入9，该函数输出2。  
**分析**对于负数`1000 0000`右移一位的时候，得到`1100 0000`而非`0100 0000`。因此如下方法对于负数会进入死循环：

int NumberOf1(int n) {
        int count=0;
        while(n){
            if(n&1) count++;
            n=n>>1;
        }
        return count;
    }

**代码实现**  
//解法一，不右移n，左移1

int NumberOf1(int n) {
        int count=0;
        unsigned int flag=1;
        while(n){
            if(n&flag) count++;
            flag=flag<<1;
        }
        return count;
    }

//解法二，基于这样一个规律：我们把一个整数减去1，都是把最右边的1变成0；并且如果它右边还有0的话，所有的0都变成1，而它左边所有位都保持不变。

int NumberOf1(int n) {
        int count=0;
        while(n){
            ++count;
            n=(n-1)&n;
        }
        return count;
    }

## 应用：不用加减乘除做加法 ##

**题目**：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、÷四则运算符号。  
**分析**：分三步：第一步只做各位相加不进位，第二步做进位，第三步将前面两个结果加起来，即重复前两位，直到不产生进位为止。  
**代码实现**

int Add(int num1, int num2) {
        int sum, carry;
        while (1) {
            sum = num1^num2;
            carry = (num1&num2) << 1;
            num1 = sum;
            num2 = carry;
            if (num2 == 0) return num1;
        }
    }

**测试用例**

Add(5, 17);
    Add(0, 17);
    Add(5, 0);

## 应用：数组中只出现一次的数字 ##

**题目**：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。  
**分析**：首先，大家都对“数组中只有一个只出现一次的数字”这个题目比较熟悉，直接遍历一遍异或即可得解。出现两个数字怎么办呢？至少有一种思路是将这个数组分为两个数组，每个数组只有一个只出现一次的数字。问题又来了，怎么得到这两个数组呢？答：异或遍历一遍，得到的即为两个只出现一次数字的异或值；这个异或值若某一位上为1，那需要找的两个数在这一位上必定不相同；因此可以根据这一位是否为1将原数组分为两个数组。  
**代码实现**

int findFirstBitOfOne(int num){
        int count=0;
        int flag=1;
        while(num & flag==0){
            count++:
            flag =flag<< 1;
        }
        return count;
    }
    
    void findNumsOnlyOnce(vector<int> array, int& num1, int& num2){
        int len=array.size();  //假设输入数据符合规则
        if(len<2){
            num1=array.at(0);
            num2=array.at(1);
            return;
        }
        int nor=0;
        for(int i=0; i<len; i++){
            nor ^= array.at(i);
        }
        int flag= 1 << findFirstBitOfOne(nor);
        num1=0;num2=0;
        for(int i=0; i<len; i++){
            if(array.at(i)&flag == 0){
                num1 ^= array.at(i);
            }
            else{
                num2 ^= array.at(i);
            }
        }
        return;
    }