位运算及模板
1.位运算的问题引出及解决方案
关于位运算，有两个常见问题。
1. 给定一个数n，对于n的二进制表示，求其第k位是几。（注意：k是从0开始编号）。
2. 编写一个函数lowbit(x),返回x的二进制表示的最后一位1(这里的x为正数/负数/0均可)。
例如：
x = 1010 lowbit(x) = 10
x = 101000 lowbit(x) = 1000
由上述案例可知：lowbit(x)返回的都是二进制数。
对于lowbit(x)函数，是日后理解树状数组的基石。lowbit(x)函数主要用来解决：一个二进制数中有多少个1这样的问题。这个问题，我们将在例题中进行讲解。
关于上述问题的解决方案如下：
1. 对于第一个问题，我们需要分两步解决：
1. 先把第k位移到最后一位：n >> k
2. 看个位是几：x & 1 (其中:x = n >> k)
把前两步综合起来，就得到了公式：
n >> k & 1
2. 对于第二个问题，只需要一个公式即可：
function lowbit(x)
return x & -x
需要注意：C++中的右移符号是看操作数是什么类型的。如果是无符号类型，那么就是逻辑右移，如果是有符号类型，那么就是算数右移。
2. 位运算模板
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
3. 例题
1. 给定一个数字n，求n的二进制，并输出
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int n;
int k = 0;
int number[100010];
scanf("%d",&n);
for(int i=0;i<32;i++){
number[i] = n >> i & 1;
}
for(int i=31;i>=0;i--){
printf("%d",number[i]);
}
return 0;
}
上述是-20在计算机中的二进制表示(补码)
https://www.acwing.com/problem/content/803/
给定一个二进制数,求其包含多少个1,我们可以采用如下做法去计算：
1. 首先通过lowbit(x)函数，找到这个二进制数的最后一个1（二进制数）。
2. 更新原来的二进制数，将lowbit(x)所得到的最后一个1减掉。[x = x - lowbit(x)]。
3. 重复上述操作，上述操作重复了多少次，二进制数里面就会有多少个1。直到二进制数中没有1为止。(即：x = 0)。
#include <iostream>
#include <cstdio>
using namespace std;
int lowbit(int x){
return x & -x;
}
int main(){
int n;
scanf("%d",&n);
int q[100010];
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
for(int i=0;i<n;i++){
int res = 0;
while(q[i]){
q[i] -= lowbit(q[i]);
res++;
}
printf("%d ",res);
}
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。