位运算
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。 注意:位运算是针对二进制的运算,所以手动模拟时要先将数转化为二进制。
常见的位运算
按位与 | a&b |
---|
按位或 | a|b | 按位异或 | a^b | 按位取反 | ~a | 左移 | a<<b | 带符号右移 | a>>b |
1、按位与
同位上,有0则0,同1则1; a: 19? ? b: 10? ? a&b: 2 为方便表示以下每个数只写8位
a | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
---|
b | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | a&b | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
2、按位或
同位上,有1则1,同0则0; a: 19? ? b: 10? ? a|b: 27
a | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
---|
b | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | a|b | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
3、按位异或
同位上,相同为0,不同为1; a: 19? ? b: 10? ? a^b: 25
a | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
---|
b | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | a^b | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
4、按位取反
每一位,1变0,0变1; a: 19? ? ~a: -20 (如果不懂负数的二进制表示看这里)
5、左移
每一位左移,右边补零; a: 19? ? a<<1: 38? ? a<<2: 76
a | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
---|
a<<1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | a<<2 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
6、带符号右移
每一位右移,左边补充最高位数(正数补1,负数补0);
正数
a: 19? ? a>>1: 9? ? a>>2: 4
a | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
---|
a<<1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | a<<20 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
负数
a: -19? ? a>>1: -10? ? a>>2: -5
a | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
---|
a<<1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | a<<2 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
代码
int a=19,b=10;
cout<<"a:19 b:10 a&b: "<< (a&b) <<endl;
cout<<"a:19 b:10 a|b: "<< (a|b) <<endl;
cout<<"a:19 b:10 a^b: "<< (a^b) <<endl;
cout<<"a:19 ~a :"<< (~a) <<endl;
cout<<"a:19 a<<1:"<< (a<<1) <<" a<<2:"<< (a<<2) <<endl;
cout<<"a:19 a>>1:"<< (a>>1) <<" a>>2:"<< (a>>2) <<endl;
a=-19;
cout<<"a:-19 a>>1:"<< (a>>1) <<" a>>2:"<< (a>>2) <<endl;
输出
位运算应用
Acwing 801.二进制中一的个数
原题链接:Acwing 801.二进制中一的个数
题目描述
给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,表示整个数列。
输出格式
共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000, 0≤数列中元素的值≤109
输入样例
5 1 2 3 4 5
输出样例
1 1 2 1 2
代码
解法1 yxc’s
#include<iostream>
using namespace std;
int lowbit(int x)
{
return x&-x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
int res=0;
while(x) x-=lowbit(x),res++;
cout<<res<<' ';
}
return 0;
}
解法2
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
int res=0;
while(x)
{
if(x&1) res++;
x=x>>1;
}
cout<<res<<" ";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
|