6127LeetCode刷题:优质数对的数目(位运算)

1. 题目描述：
   给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。
   如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：
   num1 和 num2 都 在数组 nums 中存在。
   num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。
   返回 不同 优质数对的数目。

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        //求了OR和AND后的1的个数之和 就等于原来两个数的1的个数之和
        long long res =0;
        vector<int> a(32,0); // 0~31
        for(auto i : nums){
            if(s.find(i) == s.end()){
                s.insert(i);
            }else{
                continue;
            }
            //计算i中1的个数
            int count = 0;
            int flag = 1;
            //这里采用了两种求1的个数的方法
            // for(int j = 0; j < 31;   j){
            //     if(i & (1<<j)){
            //           count;
            //     }
            // }
            for(int j = 0;j < 31;  j){
                if(i & flag){
                      count;
                }
                //flag<<=1;
                flag = flag<<1; 
            }
              a[count];
        }
        //cout << a;
        for(int i = 0;i < 32;  i){
            for(int j = max(k-i,0); j < 32;  j){
                res = res   (a[i]*a[j]);
            }
        }
        return res;
    }

private:
    unordered_set<int> s;
};

4. tips：
   进行位操作的时候，整数相当于对原码操作，负数要对补码操作
   原码：就是直观的二进制表示方式
   反码：
    正数：和原码一样
    负数：符号位不变，其余位按位取反
   补码：
    正数：和原码一样
    负数：符号位不变，反码加一
   正数二进制左移1 ，负数补码左移一，符号位不变，右端空位补零
   右移末尾舍弃，高位补符号位。
   vector<> 直接使用=赋值使用的是深拷贝。

这篇好文章是转载于：学新通技术网