[数据结构与算法]2022/01/16 位运算

1.?231. 2 的幂

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

2.?342. 4的幂

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

3.?191. 位1的个数

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

4.?面试题 16.01. 交换数字

class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }
};

5.?136. 只出现一次的数字

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

6.?461. 汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }
};

7.?693. 交替位二进制数

class Solution {
public:
    bool hasAlternatingBits(int n) {
        while(n>0){
            if(n%2==(n/2)%2)return false;n/=2;
        }
        return true;
    }
};

8.?1863. 找出所有子集的异或总和再求和

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (auto num: nums){
            res |= num;
        }
        return res << (n - 1);
    }
};

9.?371. 两整数之和

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

10.?面试题 05.01. 插入

class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        return(N>>j>>1<<j<<1)|(M<<i)|(N&((1<<i)-1));
    }
};

?