文章目录
常见的运算总结
五道基础位运算相关题目
位1的个数
解题思路：
-
理解汉明重量：
汉明重量指的是一个数的二进制表示中，1 的个数。对于一个 32 位的整数，我们需要逐位检查它的二进制表示，统计其中 1 的个数。 -
逐位检查每一位是否为 1：
因为整数在计算机中通常表示为 32 位（对于 32 位系统），我们可以通过逐位检查的方式来统计 1 的个数。
使用位运算，通过 1 << i，将数字 1 向左移 i 位，生成一个只有第 i 位为 1 的数（其余位均为 0），再与 n 进行按位与运算 n & (1 << i)。
如果 n 的第 i 位是 1，那么 n & (1 << i) 的结果会不为 0，表明该位为 1，计数器 count 加 1。
否则，该位为 0，不进行任何操作。 -
循环检查所有位：
我们只需遍历 32 位整数的每一位，通过上述的位运算进行检查。 -
时间复杂度分析：
每次需要检查一位，循环 32 次即可完成，因此该算法的时间复杂度是 O(1)，常数时间复杂度。
空间复杂度为 O(1)，因为只需要使用常数数量的额外变量。
class Solution
{
public:
// 计算一个整数 n 的汉明重量（即二进制表示中 '1' 的数量）
int hammingWeight(int n)
{
int count = 0; // 计数器，用来记录二进制中 '1' 的个数
// 遍历 32 位整数的每一位
for(int i = 0; i < 32; i++)
{
// 判断 n 的第 i 位是否为 '1'
// (1 << i) 是将 1 左移 i 位，生成一个只有第 i 位为 1，其余位为 0 的数
// n & (1 << i) 检查 n 的第 i 位是否为 1
if(n & (1 << i))
count++; // 如果第 i 位是 '1'，则计数器加 1
}
return count; // 返回二进制中 '1' 的数量
}
};
比特位计数
解题思路：
- 计算单个数的二进制表示中的 1 的个数：
要求每个数的二进制表示中 1 的个数，我们可以通过不断除以 2 来实现。每次除以 2 时，n % 2 可以判断当前最低位是否为 1。如果为 1，说明当前位是 1，我们就将计数器加 1。
重复上述过程，直到 n 等于 0 为止。 - 遍历计算所有数字的 1 的个数：
对于每个 i，我们调用前面的函数 trans2bit 来计算 i 的二进制表示中 1 的个数，并将结果存储到数组中。 - 时间复杂度：
每个数字 i 需要逐位进行计算，而数字 i 的二进制表示最多包含 log(i) 位。所以对于每个数字进行逐位计算，整体时间复杂度为 O(n log n)。
空间复杂度为 O(n)，因为我们需要返回一个长度为 n+1 的数组。
class Solution
{
public:
// 计算整数 n 的二进制表示中 '1' 的个数
int trans2bit(int n)
{
int ans = 0; // 用于存储 '1' 的数量
while(n > 0) // 当 n 不为 0 时，继续循环
{
ans += n % 2; // 如果 n 是奇数，n % 2 为 1，说明当前位为 '1'
n /= 2; // 将 n 右移一位，等效于 n = n / 2
}
return ans; // 返回 '1' 的数量
}
// 返回 [0, n] 范围内每个数字的二进制表示中 '1' 的个数
vector<int> countBits(int n)
{
vector<int> ans(n + 1); // 初始化长度为 n + 1 的结果数组
ans[0] = 0; // 0 的二进制表示中没有 '1'，结果为 0
// 从 1 开始循环，计算每个数的二进制中 '1' 的个数
for(int i = 1; i <= n; i++)
{
ans[i] = trans2bit(i); // 调用 trans2bit 计算 i 的二进制中 '1' 的个数
}
return ans; // 返回包含 [0, n] 每个数字 '1' 个数的结果数组
}
};
汉明距离
解题思路：
- 异或操作：
我们可以通过 异或操作 来找到两个整数的不同位：
当两个二进制位相同（都是 0 或都是 1）时，异或结果为 0。
当两个二进制位不同（一个是 0，另一个是 1）时，异或结果为 1。
因此，x ^ y 的结果会生成一个新数，其中的每一位反映了 x 和 y 在对应位上是否不同。
若相同，则该位为 0。
若不同，则该位为 1。 - 统计异或结果中 1 的数量：
我们需要统计异或结果中有多少个 1。每一个 1 都代表 x 和 y 在对应的位上不同。
可以通过 s & 1 来检查异或结果 s 的最低位是否为 1。如果是 1，则说明当前位不同，计数器加 1。 - 右移逐位检查：
每次检查完一位后，将 s 右移一位，继续检查下一位，直到 s 为 0，即所有的位都已经检查完毕。 - 时间复杂度：
我们最多需要检查 32 位（假设整数是 32 位的），因此该算法的时间复杂度为 O(1) 常数时间。
空间复杂度为 O(1)，因为只使用了常数个额外变量。
class Solution
{
public:
// 计算两个整数 x 和 y 之间的汉明距离
int hammingDistance(int x, int y)
{
// 使用异或操作 ^ 得到 x 和 y 的不同位（不同位会是 1，相同位会是 0）
int s = x ^ y; // s 现在存储 x 和 y 不同位的表示
int ret = 0; // 结果变量，用于记录不同位的数量
// 当 s 不为 0 时，继续循环
while(s)
{
ret += s & 1; // 检查 s 的最低位是否为 1，如果是 1 说明 x 和 y 在此位不同，ret 加 1
s >>= 1; // 右移 s 一位，继续检查下一位
}
return ret; // 返回汉明距离，即 x 和 y 的不同位的数量
}
};
只出现一次的数字——基础使用
class Solution
{
public:
// 找到数组中只出现一次的那个数字，其余数字都出现两次
int singleNumber(vector<int>& nums)
{
int value = 0; // 用于保存最终结果
// 遍历数组中的每个数字
for(auto ch : nums)
{
// 利用异或操作来找到只出现一次的数字
// 相同的数字异或结果为 0，不同的数字异或结果为该数字本身
value ^= ch;
}
// 返回最终的结果，value 中存储的是数组中只出现一次的数字
return value;
}
};
只出现一次的数字|||——这题是最后一题的简单版本
解题思路：
-
异或运算的特性：
相同数字异或为 0：a ^ a = 0。
任意数字与 0 异或为该数字本身：a ^ 0 = a。
如果我们将数组中所有数字进行异或操作，由于那些出现了两次的数字会互相抵消，最后剩下的就是两个只出现一次的数字的异或结果（记为 a ^ b）。 -
找到两个数字的不同位：
得到了两个数字 a 和 b 的异或结果后，a ^ b 的二进制中至少有一位为 1，表示 a 和 b 在该位上不同。我们可以利用这一点，将数组中的数字按照这一位进行分组：
一组的数字在这一位上为 0。
另一组的数字在这一位上为 1。
通过这种方式，两个只出现一次的数字会被分到不同的组中，而出现两次的数字仍然会被抵消。 -
分组异或：
分别对两组数字进行异或操作。由于其他数字都成对出现，它们会互相抵消，剩下的结果就是两个只出现一次的数字。
class Solution
{
public:
// 返回数组中只出现一次的两个数字
vector<int> singleNumber(vector<int>& nums)
{
int ret = 0; // 用于存储所有数的异或结果
int a = 0, b = 0; // 用于存储两个只出现一次的数字
// 第一步：将所有数字异或，最终结果是两个不同数字 a 和 b 的异或值
for(auto x : nums)
{
ret ^= x; // 所有数异或，成对出现的数会抵消为 0，剩下的就是 a ^ b
}
// 第二步：找到 ret 中的某一位为 1 的位（这表示 a 和 b 在该位不同）
int h = 1;
while((ret & h) == 0) // 找到 ret 中第一个为 1 的位
{
h = (h << 1); // h 每次左移一位
}
// 第三步：根据第 h 位是否为 1，将所有数字分为两组，分别异或
for(auto x : nums)
{
if((h & x) == 0) // 如果 x 的第 h 位为 0，则归入 a 的组
a ^= x; // 分别异或，得到的就是只出现一次的 a
else // 如果 x 的第 h 位为 1，则归入 b 的组
b ^= x; // 分别异或，得到的就是只出现一次的 b
}
// 返回结果，a 和 b 就是数组中只出现一次的两个数字
return {a, b};
}
};
面试题01.01.判定字符是否唯一
解题思路：
- 位图法：
由于字符串只包含小写字母，字母表中只有 26 个字母，因此可以用一个整数的 26 位来记录每个字母是否出现过。
利用整数的二进制位表示字母出现的状态，比如，a 对应二进制的第 0 位，b 对应第 1 位，依此类推到 z 对应第 25 位。 - 位运算检查字符是否重复：
我们使用一个变量 bitmap 来作为位图，它的每一位表示一个字母是否已经出现。
遍历字符串，对于每个字符 ch，计算它相对于 ‘a’ 的偏移量 i = ch - ‘a’，然后检查 bitmap 的第 i 位是否已经为 1。
如果该位为 1，说明该字符已经出现过，直接返回 false。
如果该位为 0，说明该字符没有出现过，将该位设为 1，表示该字符已经出现。 - 提前检查字符串长度：
如果字符串的长度大于 26，那么肯定有重复字符，因为字母表中只有 26 个字母。此时直接返回 false。 - 时间复杂度分析：
遍历字符串的每个字符，执行一次位运算，每次操作的时间复杂度为 O(1)，所以总的时间复杂度为 O(n)，其中 n 是字符串的长度。
空间复杂度为 O(1)，因为我们只用了一个整数变量来存储位图。
第二种就是利用哈希表，但是解法一更加巧妙
class Solution
{
public:
bool isUnique(string astr)
{
// 如果字符串长度大于26，则肯定有重复，因为字母表只有26个字母
if(astr.size() > 26) return false;
int bitmap = 0; // 用于记录字符出现的位置，位图初始化为0
// 遍历字符串中的每个字符
for(auto ch : astr)
{
int i = ch - 'a'; // 计算字符 ch 相对于 'a' 的位置，a=0, b=1, ..., z=25
// 检查该字符是否已经在位图中记录过
// 右移 i 位后，与1按位与，判断该位置是否为1，表示该字符是否已出现过
if(((bitmap >> i) & 1) == 1) return false; // 如果该位已经为1，说明字符重复，返回 false
// 如果该字符没有出现过，将它对应的位置1标记为已出现
bitmap |= 1 << i; // 将第 i 位设为 1，表示字符已出现
}
// 遍历完所有字符，若没有重复则返回 true
return true;
}
};
class Solution
{
public:
bool isUnique(string astr)
{
int hash[26] = { 0 }; // 定义一个长度为 26 的数组，用于存储每个字母的出现次数
// 26 表示字母表中的 26 个字母（假设字符串只包含小写字母）
// 遍历字符串 astr 的每一个字符
for(int i = 0; i < astr.size(); i++)
{
// 使用 hash 数组记录每个字母出现的次数，'a' 对应下标 0，'b' 对应下标 1，依此类推
hash[astr[i] - 'a']++; // 通过 'astr[i] - 'a'' 来获取字母在数组中的位置
// 如果某个字母出现超过一次，则返回 false，表示不是唯一的
if(hash[astr[i] - 'a'] > 1)
return false; // 当某个字母出现次数大于 1 时，返回 false
}
// 如果遍历完字符串，没有任何字母出现次数超过 1，则返回 true，表示所有字母都是唯一的
return true;
}
};
丢失的数字
解题思路：
-
异或运算的特性：
相同的数字异或为 0：a ^ a = 0。
任意数字与 0 异或为该数字本身：a ^ 0 = a。
利用这个特性，可以通过异或运算找到缺失的数字。数组中其他数字都成对出现（存在于数组和完整的 [0, n] 集合中），只有一个数字缺失，通过异或操作可以将其找到。 -
思路步骤：
首先，将数组中的所有数字依次进行异或运算，得到一个中间结果。
然后，将从 0 到 n 的所有数字进行异或运算。
最后，所有成对出现的数字通过异或操作会抵消为 0，剩下的就是那个缺失的数字。 -
时间复杂度分析：
我们只需要遍历数组两次：一次遍历 nums 数组，一次遍历从 0 到 n，每次异或操作的时间复杂度为 O(1)，因此整体时间复杂度为 O(n)。
空间复杂度为 O(1)，只使用了一个额外变量来存储异或结果。
class Solution
{
public:
// 找到 0 到 n 中缺失的数字
int missingNumber(vector<int>& nums)
{
int ret = 0; // 用于存储异或结果
// 第一步：对数组中的所有数字进行异或
for(auto x : nums)
{
ret ^= x; // 异或数组中的每一个数字
}
// 第二步：对 0 到 n 的数字进行异或
for(int i = 0; i <= nums.size(); i++)
{
ret ^= i; // 异或从 0 到 n 的所有数字
}
// 返回结果，ret 中存储的就是缺失的数字
return ret;
}
};
两整数之和
解题思路：
要实现不使用加法符号的两个数的相加，可以利用 位运算 来模拟加法操作。
核心思想：
- 异或运算 (XOR)：可以用于计算两个数的 不带进位的和。
例如：
5 (101) 和 3 (011) 的异或结果是 6 (110)，这是不考虑进位的加法结果。
与运算 (AND)：用于计算 进位信息。如果两个数在某一位上都为 1，就会在下一位产生进位。
例如：
5 (101) 和 3 (011) 的与运算结果是 1 (001)，这表示需要在下一位进位。
左移运算 (<<)：将进位信息左移一位，表示将进位加到更高位。
通过不断进行异或和与运算，逐步计算出两个数的和，直到进位为 0。
步骤：
- 使用 a ^ b 计算 不带进位的加法结果。
使用 (a & b) << 1 计算 进位信息，并将其左移一位，准备加到更高位。
重复上述步骤，直到进位信息为 0，此时 a 就是最终的加法结果。
class Solution
{
public:
// 计算两个整数 a 和 b 的和，不使用加法运算符
int getSum(int a, int b)
{
// 当进位 b 不为 0 时，继续循环
while(b != 0)
{
// c 记录 a 和 b 的不带进位的加法结果
int c = a ^ b; // 异或运算：相当于按位相加，不考虑进位
// d 记录 a 和 b 的进位信息
// 进位是通过按位与操作来计算，然后左移一位
unsigned int d = (a & b) << 1; // 按位与并左移一位：表示进位
// 更新 a 和 b：a 变成新的和，b 变成新的进位
a = c; // 将不带进位的加法结果赋值给 a
b = d; // 将进位赋值给 b
}
// 当 b 为 0 时，a 即为最终的加法结果
return a;
}
};
只出现一次的数字||
解题思路：
我们可以利用位运算来实现线性时间复杂度的解法。通过遍历 32 位整数的每一位，统计数组中每个数字在该位上 1 的个数。由于其他数字都出现了 3 次，它们在每一位的和必然是 3 的倍数，唯一一个出现一次的数字会影响这个倍数关系。
核心思想：
- 对于每一位（第 i 位），我们统计所有数字在这一位上的和，称为 sum。
如果 sum % 3 == 1，说明只出现一次的数字在这一位是 1，否则就是 0。
最终，我们通过将每一位的 1 或 0 拼接起来，得到唯一出现一次的数字。
解题步骤：
- 初始化结果变量 ret = 0，用于存储最后的结果。
对于每一位（从第 0 位到第 31 位），进行以下操作：
统计数组中所有数字在该位上 1 的个数，称为 sum。
计算 sum % 3，如果结果是 1，则说明唯一出现一次的数字在这一位上是 1。
将结果更新到 ret 中。
遍历完所有位后，ret 就是唯一出现一次的数字。
class Solution
{
public:
// 找到数组中唯一一个出现一次的数字，其他数字都出现了三次
int singleNumber(vector<int>& nums)
{
int ret = 0; // 存储结果，即只出现一次的数字
// 遍历 32 位整数的每一位
for(int i = 0; i < 32; i++)
{
int sum = 0; // 用于记录当前第 i 位的所有数字的和
// 遍历数组，统计所有数字的第 i 位的和
for(auto x : nums)
{
if(((x >> i) & 1) == 1) // 检查当前数字的第 i 位是否为 1
sum++; // 如果是 1，sum 递增
}
// 只出现一次的数字在第 i 位是否为 1 由 sum % 3 决定
sum %= 3; // 由于其他数字都出现了 3 次，它们的第 i 位之和对 3 取余会为 0
if(sum == 1) // 如果余数为 1，说明只出现一次的数字在第 i 位为 1
ret |= (1 << i); // 将第 i 位设置为 1，更新结果 ret
}
return ret; // 返回结果，即只出现一次的数字
}
};
面试题17.19.消失的两个数字
解题思路：
- 这个题目与之前的 “缺失的数字” 和 “只出现一次的数字” 题目密切相关，都是通过异或运算来处理和识别唯一的、缺失的数字。通过理解异或运算的特性，我们可以高效地解决这类问题。
相关异或运算的特性： 相同的数异或为 0：a ^ a = 0。 任意数与 0 异或结果为该数本身：a ^ 0 = a。
利用这些性质，可以将成对出现的数字互相抵消，而剩下的就是缺失的或者只出现一次的数字。
解题步骤：
-
计算整体异或：
首先我们对数组 nums 中的所有数字进行异或操作，得到一个中间结果。
然后我们再对从 1 到 n+2 的所有数字进行异或操作，将两部分结合，得到 ret，它是缺失的两个数字 a ^ b 的异或结果。 -
区分两个缺失的数字：
因为 a 和 b 是两个不同的数字，所以它们在二进制表示中一定有某一位不同。我们可以通过找到 ret 中最低位为 1 的位置 h，来区分 a 和 b。
这一位表示 a 和 b 在该位上的二进制值不同，一个是 0，一个是 1。因此我们可以根据这一位，将所有数字分为两组：
一组是该位为 0 的数字。
另一组是该位为 1 的数字。 -
分组异或：
对每一组数字分别进行异或操作，最终每一组中只会剩下一个缺失的数字。这样我们就得到了缺失的两个数字 a 和 b。
分组时，我们需要对 nums 和 1 到 n+2 这两个集合分别进行异或操作。
返回结果： -
最后，将结果 a 和 b 返回。
class Solution
{
public:
vector<int> missingTwo(vector<int>& nums)
{
int ret = 0; // 用于存储所有数的异或结果
int a = 0, b = 0; // 用于存储两个只出现一次的缺失数字
// 第一步：对 nums 中的所有数字进行异或操作
for(auto x : nums)
{
ret ^= x; // 异或 nums 中的每个数字
}
// 第二步：对从 1 到 n+2 的数字进行异或操作，结合 nums 得到 ret
for(int i = 1; i <= nums.size() + 2; i++)
{
ret ^= i; // 异或从 1 到 n+2 的每个数字
}
// ret 中存储的就是缺失的两个数字的异或结果 a ^ b
// 找到 ret 中的最低位为 1 的位 h，用于区分 a 和 b
int h = 1;
while((ret & h) == 0) // 找到最低的 1 位
h = (h << 1); // h 左移一位，直到找到 ret 中第一个为 1 的位
// 第三步：根据 h 的位对 nums 中的数进行分组异或
for(auto x : nums)
{
if((h & x) == 0) // 如果该数字的 h 位为 0
a ^= x; // 分到 a 的组，进行异或
else // 如果该数字的 h 位为 1
b ^= x; // 分到 b 的组，进行异或
}
// 第四步：根据 h 的位对从 1 到 n+2 的数字进行分组异或
for(int i = 1; i <= nums.size() + 2; i++)
{
if((h & i) == 0) // 如果该数字的 h 位为 0
a ^= i; // 分到 a 的组，进行异或
else // 如果该数字的 h 位为 1
b ^= i; // 分到 b 的组，进行异或
}
// a 和 b 就是缺失的两个数字
return {a, b};
}
};
总体总结：
通过这些题目可以看到，异或操作 在处理查找、去重和加法等问题时非常高效，尤其适合那些与数字位操作相关的场景。异或运算能够帮助我们利用数学性质简化操作，特别是在需要避免额外空间或者较高时间复杂度的情况下。对于很多经典的查找问题，位运算都是一个强大的工具，尤其在处理缺失、重复以及唯一出现的数字时表现非常出色。
标签：数字,int,复杂度,ret,异或,解题,揭秘,运算 From： https://blog.csdn.net/ZWW_zhangww/article/details/143128689