二进制位运算基础及其应用：
一、基本位运算符：
1.& 按位与：（从左到右）二进制中对应位都是1则为1，否则为0；
2. | 按位或：（从左到右）二进制中对应位有一个是1则为1，否则为0；
3. ^按位异或：（从左到右）二进制中对应位相同则为0，不同为1；
4. <<左移：右侧空位补0，二进制位数变化。
对于一个数x，x<<n等于x*2n
5. >>右移：左侧空位补符号位，二进制位数不变。
对于一个数x，x>>n等于x/2n
6. ~ 按位非：此运算比较复杂，在此详细解释：
~x等于将x的补码取反（包括符号位）后作为~x的补码，然后最终返回~x的原码
例：
1.对于正数8：
~8=-9;
8的二进制原码：00001000-->8的补码00001000-->~8补码11110111-->~8补码-1，再取反求得原码为：10001001-->所以~8=(10001001)2=(-9)10。
2.对于负数-3：
~-8=7;
-8的二进制原码：10001000-->-8的补码11111000-->~-8补码00000111-->~-8原码即为：00000111-->所以~-8=(00000111)2=(7)10。
可得出规律：任一个数的非运算都等于它的相反数减一，包括0（~0=-1）
关于位运算与二进制的实际应用：
1.求n的二进制表示中第k位（从左到右）数字是什么:
/*
1.先将第k位移到最后一位n >> k
2.看最后一位是几 & 1
*/
int bsk(int n,int k){//此函数则返回n二进制的第k位
return n>>k&1;
}2.判断x的二进制最后一位：x&1
//例如判断a的二进制最后一位，通过这种方式也可以判断奇偶（0则偶，1则奇）
int a=100;
cout<<(a&1)<<endl;3.返回x的二进制最低位1出现时所对应的值(lowbit)：
//lowbit返回x的二进制最低位1出现时所对应的值：
//在c++中 x & -x = x & (~x + 1)
int lowbit(int x){
return x&-x;
}4.上述bsk函数的应用：
#include<iostream>
using namespace std;
int bsk(int n,int k){//此函数则返回n二进制的第k位
return n>>k&1;
}
int main(){
//输出1024二进制的第1~9位:
for(int i=1;i<=10;i++){
cout<<bsk(1024,i)<<' ';
}
cout<<endl;
//截取18767二进制的第3~12位并按原二进制顺序输出:
for(int i=12;i>=3;i--){
cout<<bsk(18767,i)<<' ';
}
cout<<endl;
//输出23456的二进制：
int top=0,b[1000];
int t=23456;
while(t!=0){
b[top++]=t&1;
t>>=1;
}
while(top>=0){
cout<<b[--top];
}
cout<<endl;
}5.龟速乘：
//龟速乘：(可防止数据溢出)
ll mul(ll a,ll b,ll mod=1000000000){//求a乘b,mod表示控制输出后n位（不包括前导0），则mod为1后面跟n个0
ll ans=0;
while(b!=0){
if(b&1){//b的二进制位（最后一位）不为0，则进行
ans=(ans+a)%mod;
}
a=(a<<1)%mod; //等价于a*2%mod
b>>=1;
}
return ans%mod;
}6.快速幂：速度快，时间复杂度为O(logn).
ll qpow(ll a,ll b,ll mod){//求a的b次方,mod表示输出后n位（不包括前导0），则mod为1后面跟n个0
ll ans=1;
while(b!=0){
if(b&1){//b的二进制位（最后一位）不为0，则进行
ans=mul(ans,a)%mod;//这里用到了上面的龟速乘，防止数据溢出
}
a=mul(a,a)%mod;
b>>=1;
}
return ans%mod;
}快速幂和龟速乘原理都是一致的，都是利用二进制分解运算
7.lowbit的应用：
//统计二进制n中1的个数：
int ans=0;
int n=240;
while(n>0){
n-=lowbit(n);
ans++;
}
cout<<ans<<endl;原理为：先用原数计算出lowbit(x)，然后用原数减去这个数，再不断lowbit。
这也是树状数组的实现原理。
基于这个操作我们可以将分解出一个整数可以由哪些的2的幂相加构成。比如11110000也就是240=2^4+2^5+2^6+2^7。
以上就是二进制与位运算的全部内容了。
