位运算

位运算

​ 任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数（常数优化）。

​ C++提供了6种位运算符。

复合运算符

​ 位运算符也可以与赋值运算符组成复合运算符。

例如 a&=b 相当于a=a&b

优先级

（1）、移位运算符在乘除加减后面，在比较运算符前面 （2）、按位与、或、异或在比较运算符后面，在逻辑与、或前面

建议多用括号

应用、技巧

判断奇偶性

将二进制转成十进制的过程是一个按权值进行累加的过程。

十进制内容=1×23+0×22+0×21+1×20=101\times 2^3 +0\times 2^2+0\times 2^1+1\times 2^0=101×23+0×22+0×21+1×20=10

2的0次方是1，其他的2的幂次方都是偶数。那么一个数只要它的二进制的第000位上为1，他就一定是奇数，否则就是偶数。

if(x&1==0){//偶数
    
}else{//奇数
    
}

1的二进制是第000位上是1，其他位上是0,进行&运算时，只有两边都为1，结果才为1，只要有一个为0，结果就不为零。

消去数字二进制的最后一位1

二进制加减操作时，和十进制一样存在进位，借位的特性。不过变成了逢二进一。

若是类似这样的二进制101000010100001010000 减1，则会变成100111110011111001111

将原值与减1后的进行按位与运算，则能将最后一位的1消去。

x&(x-1)

【习题】1

• 180815 二进制表示中1的个数

利用x&(x-1)操作，不断的消去x的二进制表达中的最后一位1，当到最后，x就变成了0。消去1的操作次数也就是x的二进制表达中的1的个数。

int cnt=0;
while(x){
    x=x&(x-1);
    cnt++;
}
cout<<cnt;

判断N是否是2的幂次

二的幂次方的二进制表达一定是只有一个1，故只需要统计数字二进制中的1的个数是否等于1即可。

int cnt=0;
while(x){
    x=x&(x-1);
    cnt++;
}
if(cnt==1){
    cout<<"Yes";
}else{
    cout<<"No";
}

【习题】

• 180812 判断是否是2的整数次幂

2的次方的计算

二的幂次方的二进制表达一定是只有一个1,202^020是第0位上是1，212^121是第1位上是1，2n2^n2n是第n位上是1。我们只需将1左移到相应位数即可。

故2n2^n2n=1<<n

【习题】

• 180817 找出不大于n的最大的2的整数次幂

二进制输出

void printBin(int x,int n){
    //以n位二进制的形式输出x
    for(int i=n-1;i>=0;i--){
        cout<<((x>>i)&1);
    }
}

枚举子集

给定n个元素，输出n个元素构成的集合的所有子集。以n个连续的0/1代表第i个元素是否选中。

每个元素只有两种状态，可将其看作一个二进制位，所有元素选或不选的状态组合可用0∼2n−10\sim 2^n-10∼2n−1对应数字的二进制来描述。

以四个元素为例

cin>>n;
u=1<<n;
for(int i=0;i<u;i++){
    print(i);
}

这道题某种意义上就是“状态压缩”，将多个只有两种状态的事物的当前状态使用一个整数的二进制形式来表达，而不是状态数组。

【习题】

• 枚举子集

判断x二进制的第j位是否为1

将x的第j位右移到最右边，与1进行与运算，若第j位为1，结果为1，否则为0。

if((x>>j)&1){
    第j位为1
}else{
    第j位为0
}

将x二进制的第j位改为1，其他位不变

不管x的二进制的第j位是什么，都要将它改为1，并且其他位不能改变。

可以利用|运算。

1按位或（0/1）结果都为1，0按位或(0/1)结果都是(0/1)。

那么只需要构造出第j位为1，其他位为0的数，将这个数与要修改的数进行按位或即可。

x=x|(1<<j)

将x二进制的第j位改为1，其他位不变

不管x的二进制的第j位是什么，都要将它改为0，并且其他位不能改变。

可以利用&运算。

1按位与（0/1）结果都为（0/1），0按位与(0/1)结果都是0。

那么只需要构造出第j位为0，其他位为1的数，将这个数与要修改的数进行按位或即可。

x=x|(~(1<<j))

^性质的技巧

"a^b"按二进制位进行“异或”运算。如果两个相应的二进制位数字不相同，则该位的结果为1；否则为0。

0^x=x 0异或某个数字，结果还是那个数字。因为0^1=1,0^0=0

x^x=0 因为相同为0，不同为1。

存在“交换律”，a^b=b^a

所以,a^b^a=b

偶数个相同的数字进行异或运算，结果为0

寻找奇数次数字

利用^“偶数个相同的数字进行异或运算，结果为0”的特性，将所有的数字进行异或计算，最后剩下的就是出现奇数次的数字。

ans=0;
for(int i:1~n){
    cin>>x;
    ans^=x;
}
cout<<ans;

【习题】

• 180813 只出现一次的数字
• 180814 丢失的数
• 180851 找筷子
• 180831 格雷码

统计两个整数的二进制数中不同的数位

利用异或的特性，相同为0，不同为1，将两个数字异或，不同的二进制位就为1，相同的二进制位就为0。只需要再统计异或后数中的1的个数即可。

【习题】

• 180819 海明码

lowbit操作

lowbit(n)，非负整数n在二进制表示下"最低位的1及其后边所有的0"构成的数值。

int lowbit(int n){
    return n&(-n);
}

快速幂的处理（倍增思想）

求

的结果

typedef long long ll;
int dp[70];//dp[i]=a^{2^i}
//预处理
void init(ll a,ll b,ll p){
    int k=log2(b);
    dp[0]=a;
    for(int i=1;i<=k;i++){
        dp[i]=dp[i-1]%p*dp[i-1]%p;
        dp[i]%=p;
    }
}
ll mypow(ll a,ll b, ll p){
    int k=log2(b);
    ll ans=1;
    for(int i=k;i>=0;i--){
        if((a>>i)&1){
            ans*=dp[i]%p;
            ans%=p;
        }
    }
    return ans;
}

【习题】

• 141518 快速幂与模运算

参考

• [1] 习题来自爱思创题库

Q.E.D.