位操作总结.md

位运算的技巧

1,

if(n & 1== 1) {
    // n 是个奇数。 
} else {
    // n 是个偶数
}

2，

a=a^b; //a=a^b 
b=a^b; //b=(a^b)^b=a^0=a 
a=a^b; //a=(a^b)^(a^b^b)=0^b=b

3,

n&(n-1) // 可以去掉最后一个1
// 用于求一个数的二进制中有多少个1

4，

// 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
a ^ a = 0
a ^ 0 = a

5，

// 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
先全部^一次，找出只出现一次的两个数在位上的差异，差异位为1
然后分两组分别求两个只出现一次的数 
    vector<int> singleNumbers(vector<int>& nums) {
        int diff = 0;
        for (auto num : nums)
            diff ^= num;
        
        int right1 = 1;
        while ((diff & right1) == 0) 
            right1 <<= 1;
        
        int res1 = 0, res2 = 0;
        for (auto num : nums) {
            if ((num & right1) == 0) {
                res1 ^= num;
            } else {
                res2 ^= num;
            }
        }
        return {res1, res2};
    }

6，

// 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
对32位所有位置的所有数计算1出现的次数，如果1出现的次数不是3的倍数，说明结果数的当前位为1
// 统计32位对应的所有数字的0和1的个数，肯定要么0不是3的倍数，要么1不是3的倍数
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int num1 = 0;
            for (auto num : nums) {
                if (((num >> i) & 1) == 1)
                    num1++;
            }
            
            if (num1 % 3 == 1) {
                int tmp = 1 << i;
                res += tmp;
            }
        }
        return res;
    }    

7， 找最右边的1

int right1 = 1;
while ((diff & right1) == 0) 
    right1 <<= 1;

参考