符号 | 语法 | 名称 | 含义 |
---|---|---|---|
& |
a&b |
按位与 | 均为 1 时才是 1 ,否则是 0 ;只要有 0 ,就是 0 |
| |
a|b |
按位或 | 均为 0 是才是 0 ,否则是 1 ;只要有 1 ,就是 1 |
^ |
a^b |
按位异或 | 相同是 0 ,不同是 1 ;1^1=0^0=0 ,1^0=0^1=1 |
~ |
~x |
取反 | 每一位都取相反数 |
<< |
a<<val |
左移 | 向左移,不足补 0 ,多余去除 |
>> |
a>>val |
右移* | 向左移,不足补 0 ,多余去除* |
*特别地,对于右移运算:
#include <bits/stdc++.h>
using namespace std;
int main(){
signed a=9,b=-9;
printf("%d %d %d %d",a>>1,b>>1,a>>2,b>>2);
return 0;
// output: 4 -5 2 -3
}
257>>4
等同于 257/pow(2,4)
3<<4
等同于 3*pow(2,4)
a<<=1
代表 a*=2
;常用 a>>=1
代表 a/=2
*#include <bits/stdc++.h>
using namespace std;
int main(){
printf("%d %d",257>>4,3<<4);
return 0;
// output: 16 48
}
*同样地,特别注意右移对于负数的取整方式,负数的左移:
#include <bits/stdc++.h>
using namespace std;
int main(){
printf("%d %d\n",(-257)>>4,257>>4);
printf("%d %d",(-3)<<4,3<<4);
return 0;
// warning on line 6 colum 21: [警告] left shift of negative value [-Wshift-negative-value]
/**
* output:
* -17 16
* -48 48
*/
}
交换两数建议使用 swap()
函数(非常强大),或者定义第三个变量临时存储,较为常用。
使用和差交换或者位运算交换可能会导致溢出,不建议使用。
#include <bits/stdc++.h> using namespace std; int main(){ int a=1,b=2; a=a^b; // a^=b; b=a^b; // b^=a; a=a^b; // a^=b; return 0; }
这里用到的按位异或性质:
第7行展开写是 b'=a'^b'=(a^b)^b=a^(b^b)=a^0=a
;
第8行展开写是 a'=a'^b'=(a^b)^a=b^(a^a)=b^0=b
。
(没带 '
的是原始变量)
力扣链接:231. Power of Two
一个数是 的幂,其二进制必须是一个 1
加上若干个 0
,如 1000
。满足这个数减去 后每一位都与原数不同。如对于 的 次方 :
10000 => 16
& 01111 => 16-1
-------
00000 => 0
原理可参考#法1 - 按位与运算。
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n>0) && (n&(n-1))==0;
}
};
与#判断是否是 的幂类似,通过语句 a&(a-1)
可以消去这个数二进制最低位的 1
,以 举例:
011 10 => 14
& 011 01 => 14-1
----- --
011 00
可以看到,减去 后与前面的部分( 011
)无关(上下每位都相同),后面的部分每位都上下不同。按位与这两个数会保留前面的部分,后面的部分全部置 0
,因此涉及到的一个 1
被消为 0
。
因此,可以得出:
1
: a&(a-1)
1
: a&(~a+1)
或 a&(-a)
** 或 lowbit(x)
** -a
表示 a
的补码
class Solution {
public:
int hammingWeight(int n) {
long long int count = 0;
while(n) {
count++;
n&=(n-1);
}
return count;
}
};
每次判断最低位是否为 1
,并右移移掉最低位,直到移为 。
class Solution {
public:
int hammingWeight(int n) {
long long int count = 0;
while(n) {
count += n&1;
n>>=1;
}
return count;
}
};
转化成不用位运算的方式:
class Solution {
public:
int hammingWeight(int n) {
long long int count = 0;
while(n) {
count += n%2;
n/=2;
}
return count;
}
};
力扣链接:693. Binary Number with Alternating Bits
每次判断相邻的两位是否是 01
或者 10
。
通过对该数按位与运算 即可( 对应的二进制为 11
)。如果该数最后两位为 10
,则按位与结果为 10
;最后两位为 01
,则按位与结果为 01
。否则都不满足。
然后把该数右移 位,继续检查最后两个二进制位。
class Solution {
public:
bool hasAlternatingBits(int n) {
while(n) {
if((n&3)!=2 && (n&3)!=1)
return false;
n>>=1;
}
return true;
}
};
洛谷链接:P10118 『STA - R4』And
洛谷链接:P1226 【模板】快速幂