总言
主要内容:编程题举例,理解位运算的思想。
文章目录
- 总言
- 1、常见位运算总结
- 1.1、基础位运算
- 1.2、位图思想
- 1.2.1、给一个数n,确定它的二进制表示中的第x位是0还是1
- 1.2.2、将一个数n的二进制表示的第x位修改成 1
- 1.2.3、将一个数n的二进制表示的第x位修改成0
- 1.3、最右侧1
- 1.3.1、提取一个数(n)二进制表示中最右侧的1(lowbit)
- 1.3.2、干掉一个数(n)二进制表示中最右侧的1
- 2、判断字符是否唯一(easy)
- 2.1、题解
- 3、丢失的数字(easy)
- 3.1、题解
- 4、位1的个数(easy)
- 4.1、题解
- 4.1.1、法一:和1做“与”运算
- 4.1.2、法二:基于算术运算的模2除2
- 4.1.3、法三:n & (n - 1) 消除n最右边的1
- 4.1.4、法三衍生:找出一定范围内的整数N是否是二的幂次方。即N=2^m。
- 5、比特位计数(easy)
- 5.1、题解
- 6、汉明距离(easy)
- 6.1、题解
- 7、两整数之和(medium)
- 7.1、题解
- 8、只出现一次的数字(easy)
- 8.1、题解
- 9、只出现一次的数字 Ⅲ(medium)
- 9.1、题解
- 10、只出现一次的数字 Ⅱ(medium)
- 10.1、题解
- 11、消失的两个数字(hard)
- 11.1、题解
- Fin、共勉。
1、常见位运算总结
1.1、基础位运算
详细版本:操作符详解
移位操作符: 作用在二进制位上,操作数只能是整数。
<< 左移操作符 :左移操作符,左边抛弃,右边补0
>> 右移操作符 :分逻辑右移和算术右移两种。
a、对逻辑右移:左边用0填充,右边丢弃。
b、对算术右移:左边用原该值的符号位填充,右边丢弃。
位操作符: 作用在二进制位上,操作数只能是整数。
& 按位与:按二进制位与。有0为0,全1为1
| 按位或:按二进制位或。有1皆为1
^ 按位异或:按二进制位异或。相同为0,相异为1。异或的本质是无进位相加。
~ 按位取反:按二进制位取反。包含符号位
1.2、位图思想
位图相关链接。
1.2.1、给一个数n,确定它的二进制表示中的第x位是0还是1
(n >> x) & 1;
(1 << x) & n;
1.2.2、将一个数n的二进制表示的第x位修改成 1
n |= (1 << x);
1.2.3、将一个数n的二进制表示的第x位修改成0
n &= ~(1 << x);
1.3、最右侧1
1.3.1、提取一个数(n)二进制表示中最右侧的1(lowbit)
n & (-n);
lowbit()
函数:用来取一个二进制最低位的1与后边的0组成的数
int lowbit (int x){
return x&-x;
}
例如:
lowbit (13) = 1 ( 13 二进制表示为 1101 ——> 1(1) )
lowbit (12) = 4 ( 12 二进制表示为 1100 ——> 4(100) )
基本应用:借助 lowbit 函数判断整数 n 是否是2的方幂
int lowbit(int x)
{
return x&(-x);
}
int chk(int n)
{
if( lowbit(n) == n ) return 1; //n是2的方幂
else return 0; //n不是2的方幂
}
结论:如果一个数n是【2的幂】,那么有lowbit(n) = n
的性质(2的幂的二进制表示中必然是最高位为1,低位为 0)
1.3.2、干掉一个数(n)二进制表示中最右侧的1
n & (n-1);
这个表达式的一个 常见用途是检查一个数是否是2的幂。一个数是2的幂当且仅当它的二进制表示中只有一个1(在最高位)。对于这样的数,n & (n-1)
的结果将是0,因为 n-1 的所有低位都是1,而 n 的所有低位都是0。所以,n & (n-1) == 0 可以用来检测一个数是否是2的幂。
1、
当n=4时,二进制为:0100
n-1=3,二进制为:0011
则:n&(n-1)==0 解释(将0100最右边的1变为0 则 0000=0)
2、
当n=8时,为1000
n-1=7,为0111
则n&(n-1)==0
3、
当n=5,为0101
n-1为0100
则n&(n-1)=0100=4!=0 解释(将0101最右边的1变为0 则 0100=4)
但需要注意,①如果 n 是0,那么 n & (n-1) 将是未定义的,因为 n-1 会是-1,而在有符号整数中,-1的二进制表示通常是全1(这取决于具体的计算机系统和编程语言)。所以,在使用这个表达式之前,你可能需要检查 n 是否大于0。 或者,②如果你正在使用无符号整数,那么当 n 为0时,n-1 将是最大的无符号整数(所有位都是1),但即使在这种情况下,n & (n-1) 也将是0,这仍然可以用来检测 n 是否是1(在无符号的情况下,1是唯一的2的幂且满足 n & (n-1) == 0 的数)。但是,通常我们更关心的是正整数是否是2的幂。
2、判断字符是否唯一(easy)
题源:链接
2.1、题解
1)、思路分析
1、暴力解法: 可以固定字符串中某一字符,遍历其它字符做比较,如此重复直至获取结果。时间复杂度为:
O
(
n
2
)
O(n^2)
O(n2)
2、哈希表: 26个英文字母,可以使用一个哈希数组hash[26]
遍历映射字符串,当hash[i]>=1时表示字符串中元素重复。时间复杂度为:
O
(
n
)
O(n)
O(n),空间复杂度为:
O
(
n
)
O(n)
O(n)
3、位图: 是在哈希数组上的优化。实则我们并不需要知道具体字符值,只是要判断该字符是否存在,即两种状态:存在、不存在。那么完全可以使用位图的思想,一个比特位有0、1两种状态,刚好可判断字符是否存在,因此只需要使用一个整型变量Int
(32bit)充当哈希表,就能满足对26个英文字符存在状态的判断。 时间复杂度为:
O
(
n
)
O(n)
O(n),空间复杂度为:
O
(
1
)
O(1)
O(1)
2)、题解
下述除了借助位图思想,还使用到了鸽巢原理。由于小写英文字母只有26位,当字符串长度超过26时,必然会有重复字符。
class Solution {
public:
bool isUnique(string astr) {
if (astr.size() > 26)
return false; // 鸽巢原理:英文字母最多26位,超过则表明其中含有重复
int bitset = 0; // 位图,哈希结构,用于统计这26个字母
for (auto s : astr)
{
int index = s - 'a';
// 判断该字符是否在位图中(判断某一位是否为1)
if (bitset & (1 << index))
return false; // 若在则返回
else
bitset |= (1 << index); // 不在则将其加入位图,继续新一轮判断(将某一位改为1)
}
return true;
}
};
3、丢失的数字(easy)
题源:链接
3.1、题解
1)、思路分析
此题解法很多,这里只做部分列举:需要注意这里[0, n]
的数组,有 n+1个数,而给定的vector<int>& nums
中只含n个数。
1、借助哈希表: 遍历数组nums,将其中出现的元素统计入哈希表中hash[n+1],再次遍历哈希表找出个数为0的元素。
2、高斯求和: 高斯求和是数学中一种经典的求和方法,由数学家卡尔·弗里德里希·高斯首次提出。对于连续的自然数序列[ 1 , 2 , 3 , … , n ],高斯求和的公式可以用来直接计算其总和。其基本形式如下:
s
=
1
+
2
+
3
+
…
…
+
n
=
n
⋅
(
n
+
1
)
2
s=1+2+3+……+n = \frac{n·(n+1)}{2}
s=1+2+3+……+n=2n⋅(n+1)。我们可以用高斯公式计算出 n+1的 总和,再与数组nums的元素总和做差,即可得出缺失数。
3、位运算: 借助了异或的性质。a^a = 0
;a^0=a
。遍历一遍数组nums,异或所有元素,再遍历一遍[0,n]的所有元素,最终结果即缺失值。
2)、题解
以下写法中一次将nums和[0,n]的数全异或了。写法多种,可看个人风格。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0;
int n = nums.size();//数组个数
for (int i = 0; i < n; ++i) {
sum ^= nums[i];//异或数组中的元素
sum ^= i;//异或0~n
}
return sum ^= n;//异或n+1
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
for (auto x : nums)//异或数组中的所有数
ret ^= x;
for (int i = 0; i <= nums.size(); i++)//异或 [0, n] 中的所有数
ret ^= i;
return ret;
}
};
4、位1的个数(easy)
题源:链接
4.1、题解
4.1.1、法一:和1做“与”运算
常规思路:从n的最后一位开始,和1做“与”运算,如此循环32次,依次判断每一位的值。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for (int i = 0; i < 32; ++i) {
if ((1 << i) & n)
count++;
}
return count;
}
};
4.1.2、法二:基于算术运算的模2除2
如下: n % 2 == 1
可以检查n 的最低位是否为1 。% 取模运算符,对于任何整数 x,x % 2 的结果要么是0(如果 x 是偶数),要么是1(如果 x 是奇数),因此,n % 2 会给出 n 的最低位的值。而n / 2
相当于将 n 的二进制表示右移一位。这样,下一次迭代将检查 n 的下一个最低位。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
if (n % 2 == 1)
count++;
n /= 2;
}
return count;
}
};
4.1.3、法三:n & (n - 1) 消除n最右边的1
利用 n & (n - 1)
来消除n最右边的1,然后如果n还是不等于0的话,让count++,同时继续消除n最右边的1。此方法中,n有多少个1就遍历多少次,相比于前两种(从头遍历到尾,每一个元素都要判断一遍)更快。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n)
{
n&=(n-1);//消除一次最右侧1
++count;
}
return count;
}
};
关于n&(n-1)的思路解析:(以169为例)
-----------------------
第一轮:n=169; n-1=168;
//1010 1001---n
//1010 1000---n-1
n=n&(n-1)=1010 1000//对n的二进制,去掉末尾1
-----------------------
第二轮:n=168; n-1=167;
//1010 1000---n
//1010 0111---n-1
n=n&(n-1)=1010 0000//对n的二进制,再去掉一个末尾1
-----------------------
第三轮:n=160; n-1=159;
//1010 0000---n
//1001 0000---n-1
n=n&(n-1)=1000 0000//对n的二进制,再去掉一个末尾1
-----------------------
依次类推,最终结束时n为零,总轮数即n的二进制上1的总数。
4.1.4、法三衍生:找出一定范围内的整数N是否是二的幂次方。即N=2^m。
此题就能运用n&(n-1)
:
当N是2的幂次方时,它的二进制表示中只有一个1,其余位都是0。
当我们对N执行减1操作(N - 1)时,这个1会变成0,而它右边的所有0都会变成1。
因此,将原数N和N - 1进行按位与操作(n & (n - 1)),由于N中的那个1在N - 1中变成了0,并且N中1右边的所有0在N - 1中都变成了1,所以这个按位与操作的结果一定是0。
而这个性质只对2的幂次方数成立。对于任何不是2的幂次方的数,其二进制表示中至少有两个1,这样n & (n - 1)的结果不会是0。
如此可快速获取结果。
此外还有一些其它方法:
①、检查二进制表示中是否只有一个1: 通过不断地将整数与1做按位与操作,并右移来实现。
②、利用数学性质直接计算: 由于2的幂次方是已知的(2, 4, 8, 16, 32, …),可以直接计算出一定范围内所有的2的幂次方数。
5、比特位计数(easy)
题源:链接
5.1、题解
这里需要注意求的是[0,n]中所有数的各自情况。
法一:逐个计算[0,n]中各元素的1个数。但相对的,每更换元素,都要从头开始重新统计。
class Solution {
public:
vector<int> countBits(int n) {
if(n == 0) return {0};
vector<int> ans(n+1);
for(int i = 0; i <= n; ++i)
{
int count =0;
int j = i;
while(j)
{
j &= (j-1);
count++;
}
ans[i] = count;
}
return ans;
}
};
法二:动态规划(后续学习)
class Solution {
public:
vector<int> countBits(int num) { // 布赖恩·克尼根算法 + DP,其实本身计算1的个数不难,但是加上DP就比较巧妙
vector<int> result(num + 1, 0);
for (int i = 1; i <= num; i++) {
result[i] = result[i & (i - 1)] + 1; // result存储的就是对应数字的1的个数
}
return result;
}
};
6、汉明距离(easy)
题源:链接
6.1、题解
是上述汉明重叠的系列题,只是这里求的是汉明举距离。
class Solution {
public:
int hammingDistance(int x, int y) {
int temp = x ^ y;
int ret = 0;
while(temp)
{
temp&=(temp-1);
ret++;
}
return ret;
}
};
7、两整数之和(medium)
题源:链接
7.1、题解
1)、思路分析
异或 ^
进行无进位加法;
按位与 &
操作能够获取进位;
可根据上述两步,不断循环进行,直到进位变成 0 为止。
2)、题解
class Solution {
public:
int getSum(int a, int b) {
while (b) {
int ret = a ^ b;
unsigned int carry = (unsigned int)(a & b) << 1;
a = ret;
b = carry;
}
return a;
}
};
8、只出现一次的数字(easy)
题源:链接
8.1、题解
解法类似于丢失的数字,利用异或的性质。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (int n : nums)
ret ^= n;
return ret;
}
};
9、只出现一次的数字 Ⅲ(medium)
题源:链接
9.1、题解
我们知道按位异或,相同为0,相异为1。
既然如此,站在二进制比特位的角度,假设该数组中只出现一次的两个元素分别为A、B(A≠B)。由于两数不同,那么A ^ B后,至少有一个二进制上的数位在异或后为1。
这样一来,以该非零的二进制位为界,可将数组中所有元素分为两组:①该数位上为0的数是一组,②为1的数分是另一组,如此一来A、B两数就会分离进入不同组中。 至于数组其余的数,虽不清楚最终落在何组,但同一元素(无论有多个个)都会被分配到相同组中,不存在既出现在A组,又出现在B组的情况。
例如:1、1 、2、2、3、4、4、5、6、6
。对3 ^ 5
,二进制为011 ^ 101 =110
。二进制两高位都为1,可任取两高位的其中一位来分类,此处我们选取第二位,如此一来,对数组所有元素,可分为:1、1、4、4、5
(A组); 2、2、3、6、6
(B组)。
如此一来,再用按位与操作符就能找出对应元素。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
long long sum = 0;// 例子:[1,1,0,-2147483648]
for (auto e : nums) // 获取所有元素的异或值:结果为 a^b
sum ^= e;
// 以a^b的某个数值为1的比特位作为基准,对nums中的所有元素遍历分组
int mark =sum &(-sum); // 这里直接以最低位1为基准值
int a = 0; // 这里分组不必使用容器来存储,直接在获取到元素时将其按位异或(求值)
int b = 0;
for (auto e : nums) {
if (e & mark)
a ^= e;
else
b ^= e;
}
return {a, b};
}
};
10、只出现一次的数字 Ⅱ(medium)
题源:链接
10.1、题解
1)、思路分析
设要找的数位 ret 。由于整个数组中,需要找的元素只出现了「⼀次」,其余的数都出现的「三次」,因此我们可以根据所有数的「某⼀个比特位」的总和 %3 的结果,快速定位到 ret 的「⼀个比特位上」的值是0 还是 1 。这样,我们通过 ret 的每⼀个比特位上的值,就可以将 ret 给还原出来。
2)、题解
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;//用于记录目标值
for(int i = 0; i < 32; ++i)
{
int sum = 0;//用于统计当前比特位总和
for(auto n: nums)//遍历数组将所有元素的第i个比特位累加
{
if(n & ( 1 << i)) sum++;//因为只有1是有效数,这里取巧只用统计1
}
if(sum % 3)//若取模结果为1,说明ret中当前为i的比特位为1
ret |= (1 << i );//(因ret本身就是0,所有位最初均为0,故对结果为0的比特位没做处理)
}
return ret;
}
};
11、消失的两个数字(hard)
题源:链接
11.1、题解
1)、思路分析
是只出现一次的数字Ⅲ和消失的数字的结合。
1、将nums和[1,n]中所有元素异或,可得消失的两数异或值:a^b
。于是问题就变成了:有两个数出现了一次,其余所有的数出现了两次。
2、那么重复只出现一次的数字Ⅲ的操作即可:定位一个比特位为1的值,根据它将nums、[1,n]分为两组,再次异或求得独立的a、b值。
2)、题解
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
//获取a^b:遍历nums数组、[1,N]区间所有元素(因重复出现两次,故按位异或后只剩下出现一次的数)
int size = nums.size();
int sum = 0;
for(auto e: nums) sum ^= e;
for(int i = 1; i <= size+2; ++i)
sum ^= i;
//定位a^b中某个数值为1的比特位:这里定位最右1
int mark = sum & (-sum);
//以该比特位,将nums数组、[1,N]内所有元素分组
int a = 0; int b = 0;
for(auto e:nums)
{
if(e & mark) a ^= e;
else b ^= e;
}
for(int i = 1; i<= size+2; ++i)
{
if(i & mark) a ^= i;
else b ^= i;
}
//返回结果
return {a,b};
}
};