C/C++神奇的位运算

神奇的位运算"/>

C/C++神奇的位运算

常用的技巧

位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：“∧”按位异或、“&”按位与、“|”按位或、“∼”取反、“<<”算术左移和“>>”算术右移。以下是一些常见的位运算特性，其中 0s 和 1s 分别表示只由 0 或 1构成的二进制数字。

x ^ 0s = x       x & 0s = 0           x | 0s = x
x ^ 1s = ~x      x & 1s = x           x | 1s = 1s
x ^ x = 0        x & x = x            x | x = x

除此之外，n & (n - 1) 可以去除 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，减去 1 得到 11110011，这两个数按位与得到 11110000。n & (-n) 可以得到 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，取负得到00001100，这两个数按位与得到 00000100。还有更多的并不常用的技巧，若读者感兴趣可以自行研究，这里不再赘述。

位运算基本问题

461.汉明距离

题目描述

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

给定两个十进制数字，求它们二进制表示的汉明距离（Hamming distance，即不同位的个数）。

输入输出样例

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

代码实现

class Solution {
public:int hammingDistance(int x, int y) {int diff = x ^ y, ans = 0;while (diff) {ans += diff & 1;diff >>= 1;}return ans;}
};

二进制特性

342.4的幂

题目描述

给定一个整数，判断它是否是 4 的次方。

输入输出样例

输入：n = 16
输出：true

代码实现

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

338.比特位计数

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入输出样例

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

题解

本题可以利用动态规划和位运算进行快速的求解。定义一个数组 dp，其中 dp[i] 表示数字 i 的二进制含有 1 的个数。对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数则为 dp[i-1] + 1；如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即dp[i>>1]。

代码实现

class Solution {
public:vector<int> countBits(int n) {vector<int> dp(n+1,0);for(int i=1;i<=n;i++){dp[i]=i&1?dp[i-1]+1:dp[i>>1];}return dp;}
};

参考资料：代码随想录