位运算
1.有一些实际的问题, 用位运算可以比较巧妙的解答, 同时复杂度非常低
2.位运算部分是 CS 很有魅力的一部分, 是一种优雅的黑科技
& 运算
1.n & (n-1) 消除二进制数的最后一个1
n & (n-1) 操作会消除原有的数子n的二进制表示的最后一个1
n ..110[1]00
n-1 ..110[0]11
n&(n-1) ..110[0]00
比如 对于1111(15)
1111 & 1110 = 1110
1110 & 1101 = 1100
1100 & 1011 = 1000
1000 & 0111 = 0
^ 运算
假设有非0数字n, 异或操作^具备一个比较奇妙的性质, 数字n遇到它自己直接一碰就没了成为0, 遇到0一碰就是它自己;
1.n ^ n = 0
2.n ^ 0 = n
例如对于
11101
^
00000
=
11101
比如对于一个数组, 其它数字都是成对出现, 只有1个数字是单独出现, [2,2,3,3,4,4], 逐个^异或下来只剩下下1个独苗
191.位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。示例 1：输入：n = 00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。
分析:
1.利用 n & (n-1) 可以消除最后一个 1, 因此可以不断的将元数字 n 和 (n-1) 进行 & 操作, 直到原来的数字变为0
比如 对于1111 = 15
1111 & 1110 = 1110
1110 & 1101 = 1100
1100 & 1011 = 1000
1000 & 0111 = 0
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n != 0) {
n = n & (n - 1);
++ans;
}
return ans;
}
};
231.2的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：输入：n = 1 输出：true 解释：2^0 = 1
示例 2：输入：n = 16 输出：true 解释：2^4 = 16
示例 3：输入：n = 3 输出：false
示例 4：输入：n = 4 输出：true
示例 5：输入：n = 5 输出：false
分析:
1.如果一个数字是 2 的幂, 那么它的2进制表示有且仅有 1 个 1
2.只利用一次 n & n-1 == 0, 表示原来的数 n 只有 1 个 1
3.对于十进制16, 二进制10000, 10000 & 01111 == 0
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
// 注意这里判断等号需要借助括号显示设定优先级
if ((n & (n-1)) == 0) {
return true;
}
return false;
}
};
136.只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：输入：nums = [2,2,1] 输出：1
示例 2 ：输入：nums = [4,1,2,1,2] 输出：4
示例 3 ：输入：nums = [1] 输出：1
分析:
1.把数字通通想成二进制数来思考问题, 不要思考任何十进制的数字
2.一个数字和另一个数字异或一次, 得到的是和原数字不同的位的标记, 然后再重复一次, 就会全部还原回来; 直觉上可以这么理解, 和我相反的相反, 那不就是我吗?
3.比如 1,2,2, 二进制结果为 01 ^ 10 = 11 然后 11 ^ 10 = 01 异或1个同样的数字两次, 相当于还原回来
4.因为数组里面设定很特殊, 除了一个数字单独以外, 其他的都是成对出现, 因此对所有数组过一遍异或, 剩下的就是只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto& n : nums) {
ans ^= n;
}
return ans;
}
};
268.丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
分析:
1.因为是连续数字, 直接求和然后逐个减去, 剩下的就是缺失数字
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = (1 + n) * n / 2;
for (auto & n : nums) {
sum -= n;
}
return sum;
}
};
2.用位运算咋做?
转载请注明来源, from goldandrabbit.github.io
