【位运算题解3】

LC中等题1

题目描述：461.汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给定两个整数 X 和 y , 计算并返回它们之间的汉明距离

（1）1010 ^ 0011 = 1001
（2）相当于两个数进行异或运算 ，结果位1的个数，就是汉明距离

代码详解C++：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int n = (x ^ y);
        int c = 0;       //计数器
        while(n) {
            n &= (n-1);  //进行与运算消去1
            ++c;
        }
        return c;
    }
};

LC中等题2

题目描述：693. 交替位二进制数
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

（1）二进制11 = 十进制 3
（2）做法就是n不断右移1位，与11进行与运算，当结果为11或00的时候就说明存在两个相邻位置的数字是相同的。

（3）举例：当 n = 0101101 时，当右移两位后 n = 01011，这时01011 & 11 =3 ，这就检测出了相邻位相同的情况。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        while(n) {
            if ((n & 3) == 3 || (n & 3) == 0) {
                return false;
            }
            n >>= 1;
        }
        return true;
    }
};

LC中等题3

题目描述：1863. 找出所有子集的异或总和再求和
给定一个整型数组，求出数组中每个子集的异或总和，计算并返回这些值相加之和。

思路：
（1） 集合子集数目是 2ⁿ 个，判断每个集合二进制1的位置，将该位置的数进行异或。

（2）将每个集合的异或结果进行相加。

举例：

int subsetXORSum(int* nums, int numsSize){
     int i, j, ans;
     int sum = 0;
     for (i = 0; i < (1 << numsSize); i++) {   //0 ~ 2^n -1 枚举每个子集
         ans = 0;
         for(j = 0; j < numsSize; j++){        //判断每个集合二进制数第0位到第n-1位之间1的位置
             if(i & (1<<j)) {
                 ans ^= nums[j];               //如果从低到高第j为1，就说明集合中存在nums[j]
             }
         }
         sum += ans;                           //将每个集合的异或值相加
     }
     return sum;
}

LC中等题4

题目描述：371. 两整数之和
给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

思路：
（1） 两数相加可以看成，带进位的加和加上不带进位的加和。

（2）不断进行递归，直到没有进位时，异或可以看成两数之和时，终止。

举例：
不带进位的加和： a ^ b = 1000 ^ 1010 = 0010
带进位加和的值：(a & b) << 1 = (1000 & 1010) << 1 = 10000

求：a + b = 10010，也就是：

由于需要一直进行加法，所以要不断通过递归进行，递归的终止条件是b=0,也就是没有进位，那么异或就是两数之和。

int getSum(int a, int b){
     return b == 0 ? a : getSum(a ^ b, (unsigned int)(a & b) << 1);
}

! ! ! LC中等题5

题目描述：面试题 05.01. 插入
给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。

编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。

思路：
（1）先将N的 i ~ j 位都归 0，为N’
（2）再将M左移i位 与 N’ 进行 或运算
举例：
N = 1010101111 M = 101
将 N 的 i~j 位归 0，采用与运算，详细见代码吧😎

class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        int ans;
        for (int k = i; k <= j; k++) {
            N &= ~(1 << k);  //将第K位为0的数与N进行与运算，消去第k位的1
        }
        return N | (M << i);
    }
};