作用于整数类型的运算对象,对二进制数位进行运算。
位与:&
当且仅当两个运算对象都为1时,该位为1
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
eg: 255 & 128 = 128
位或:|
当且仅当两个运算对象都为0时,该位为0
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
eg: 255 | 128 = 255
位取反:~
将1置为0,将0置为1
~ 1 = 0
~ 0 = 1
eg: ~ 128 = 127
位异或:^
当且仅当两个运算对象中只一个为1时,该位为1
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
eg: 255 ^ 128 = 127
左移: <<
将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。
左边二进制位丢弃不包括1时, 左移1位相当于乘以2。
eg: 3 << 2 = 12 (1100)
右移: >>
将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃.
右移1位相当于除以2(整数除法)。
eg: 7 >> 1
变成 3,也就是111 >> 1
变成了 11。
位运算的性质
-
x ^ x = 0
: 自己与自己做异或一定为0 -
x ^ 0 = x
: 一个数与0做异或还是它本身
位运算的应用:
Info位运算的应用较多,写法种类也有多种。下面的应用,建议大家只是在本地都要运行一遍,加深记忆。
此外考场上难免会有不知道的位运算应用,这个时候,手算,对比,找规律,就是最好的方式。
-
取末位(
x & 1
) 可用来判断奇数、偶数 -
操作x的第j位(从右向左数,最右边是第0位)
x | (1 << j) //将 x 的第 j 位设置为1
x & ~(1 << j) //将 x 的第 j 位设置为0
x ^ (1 << j) //将 x 的第 j 位取反
(x >> j) & 1 //取 x 的第 j 位
-
交换两个数:
a ^= b ^= a ^= b;
-
lowbit 运算
int lowbit(int x) {
// 计算 x 的二进制中,最低位的 1 以及后面所有 0 组成的数。
// lowbit(0b01011000) == 0b00001000
// ~~~~^~~~
// lowbit(0b01110010) == 0b00000010
// ~~~~~~^~
return x & -x; // CSP中考过lowbit另一种写法 x&(x^(x-1))
}
- 计算1的个数
// 求 x 的二进制中1的个数
int popcount(int x) {
int cnt = 0;
while (x) {
cnt++;
x -= x & -x;
}
return cnt;
}
- 枚举子集 给定n个元素,问这n个元素组成的每一个集合的所有子集。(n≤15)
for (int S=1; S<(1<<n); ++S){
for (int S0=(S-1)&S; S0; S0=(S0-1)&S)
//do something.
}
测试程序
这里给出一个可以用来直观展示位运算运算数和运算结果的程序,当你对位运算不熟悉的时候,可以拷贝这段代码,在本地稍加改造后运行。
cpp
#include <bits/stdc++.h>
using namespace std;
int f(int a, int b){
return a | (1 << b);
}
void otp(int x){
for (int i = 31; i >= 0; i--) printf("%d", (x >> i) & 1);
}
int main(){
int a, b; scanf("%d%d", &a, &b);
- 思考题:下面4种操作的含义是什么?
x & (x + 1);
x & (x - 1);
x | (x + 1);
x | (x - 1);
标签:运算,int,lowbit,eg,128,cpp
From: https://www.cnblogs.com/luliusheng/p/17859004.html