常见位运算总结

目录

常见位运算总结

191:位1的个数

338：比特位计数

461:汉明距离

136：只出现一次的数字

260：只出现一次的数字III

常见位运算总结

191:位1的个数

链接：191. 位1的个数 - 力扣（LeetCode）

class Solution {
public:
    int hammingWeight(int n) 
    {
        int cont = 0;

        while(n)
        {
            cont++;
            n &=(n-1);//将最右侧的1变为0
        }

        return cont;
    }
};

338：比特位计数

题目链接：338. 比特位计数 - 力扣（LeetCode）

class Solution {
public:
    vector<int> countBits(int n) 
    {
        vector<int> ret;
        for(int i = 0; i <= n; i++)
        {
            int num = i;
            int cont = 0;
            while(num)
            {
                cont++;
                num &= num-1;
            }
            ret.push_back(cont);
        }   

        return ret;
    }
};

461:汉明距离

题目链接：461. 汉明距离 - 力扣（LeetCode）

class Solution {
public:
    int hammingDistance(int x, int y) 
    {
        int num = x ^y ;//相同为0，相异为1
        int cont = 0;
        while(num)
        {
            cont++;
            num &= num-1;
        }
        return cont;
    }
};

136：只出现一次的数字

题目链接：136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int val  =0;
        for(int x : nums)
        {
            val ^= x;
        }
        return val;
    }
};

260：只出现一次的数字III

题目链接：260. 只出现一次的数字 III - 力扣（LeetCode）

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        int sum = 0;

        //两个不同的数字，这两个数字肯定有相异的地方
        //相异为1，所以sum二进制中会有两个地方有1
        //可以把这两个不同的数字分开
        for(auto& e : nums)
            sum ^= e;
        
        //考虑[-1,0][0,1]的情况，可能结果只有一个1
        int n = (sum == INT_MIN) ? sum : (sum &(-sum));
        
        int sum1 = 0,sum2 = 0;
        for(auto& e : nums)
        {
            if(e & n)
                sum1 ^= e;
            else
                sum2 ^= e;
        }

        return {sum1,sum2};
    }
};