定义

例题

剑指Offer15

求长度为32的二进制串中1的个数

基础思路：利用位运算中的与一位一位的比较，然后记录1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n){
        count += n & 1;
        n >>= 1;
        }
        return count;
    }
};

优化：利用n-1 & n减少运算时间

假设 n = 00000000000000000000000010010000

n - 1 = 00000000000000000000000010001111

n & n-1 = 00000000000000000000000010000000

这样在运算过程中，只有减法和与运算，丢弃了移位，降低了时间复杂度

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n){
        n &= n - 1;
        count++;
        }
        return count;
    }
};

剑指Offer56-1

求一个数组中只出现过一次的两个数字，其余数字都出现过两次

思路：在知道求两个数字之前，我们的先学会如何求一个数字，那就是利用异或，前面已经提到了两个相同的数字异或的结果为0，并且0异或任何数字还是等于那个数字，所以求一个数字我们只需要遍历数组进行异或即可得到一个不同的数字。

但是现在我们有两个数字，那么我们就要考虑将这两个数字分开来，我们知道两个不同的数字用二进制表示的时候肯定在某一位上的数字不同，我们只需要找到这个不同的数位置，然后利用这个条件将数组分成两个只有一个不同数字的数组，分别异或就可以得到结果。

现在我们的问题就变成了如何找到这两个数字的二进制表示时的不相同数字的位置，同样我们可以利用异或这个特性。两个不同数字异或之后，为1的那一位就是两个不同数字的位置。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = 0;
        //异或两个不相同的数字
        for(int num : nums){
            n ^= num;
        }
        //寻找不相同的位置
        int m = 1;
        while((m & n) == 0){
            m <<= 1;
        }
        //利用不相同的位置进行分组并求得两个数字
        int a = 0, b = 0;
        for(int num : nums){
            if(num & m){
                a ^= num;
            }else{
                b ^=num;
            }
        }
    }
};

剑指Offfer56-2

求一个数组中只出现过一次的数字，其余数字都出现过三次

思路：若一个数字出现过三次，则这个数字在二进制表示下每位数相加后的个数都是三的倍数，如果将数组中所有的数用二进制表示，每位数相加后余3即可得到这个数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bits(32,0);
        for(auto num : nums) {
            for(int i=0;i<32;i++) {
                bits[i] += num & 1;
                num >>= 1;
            }
        }
        int res = 0;
        for(int i=31; i>=0; i--) {
            res <<= 1;
            res += bits[i] % 3;
        }
        return res;
    }
};

剑指Offer65

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

思路：不用四则运算符号，我们很快可以联想到数字逻辑中学到的全加器，只需要通过位运算就可以得倒两数之和

这里列一下全加器的真值表

class Solution {
public:
    int add(int a, int b) {     
        while(b!=0)
        {
        //保存进位值
        int c=(unsigned int)(a&b)<<1;//C++中负数不支持左移位，因为结果是不定的
        //保存不进位值
        a^=b;
        //如果还有进位，再循环，如果没有，则直接输出没有进位部分即可。
        b=c;   
        }
        return a;
    }
};

总结

位运算其实就是我们在数字逻辑中学到的各种门电路，掌握常用位运算符号的使用对于此类的算法题就能迎刃而解了。