位运算基础
作者：blue
时间：2024.3
1.计算二进制中1的个数
n=n&(n-1) //用就完了
#include <iostream>
using namespace std;
int count(int n)
{
int sum=0;
while(n)
{
n=n&(n-1);
sum++;
}
return sum;
}
int main()
{
int n;
int sum=0;
cin>>n;
sum=count(n);
printf("%d",sum);
return 0;
}
虽然有一半的测试数据会超时，但是强在代码容易写，而且不用思考，先拿一半分数再说
#include <iostream>
#define int long long
using namespace std;
int count(int n)
{
int sum=0;
while(n)
{
n=n&(n-1);
sum++;
}
return sum;
}
signed main()
{
int n,k;
int ans=0;
int sum;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
sum=count(i);
if(sum==k) ans++;
}
printf("%lld",ans);
return 0;
}
2.位运算（x & -x）
~x:按位取反
-x 的值， 其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得
x & -x == x & (~x + 1)
x 为偶数
偶数按位取反后一定是奇数，再+1，会影响进位。
如 0000 0100 1110， 取反后的结果就变成了 1111 1011 0001，而当这个值 + 1之后由于发生了进位， 即
1111 1011 0001 + 1 = 1111 1011 0010
这个结果再与最初的值相与后， 只会有一位保留为1
0000 0100 1110 & 1111 1011 0010 = 0000 0000 0010
如果一个偶数， 在执行 x & -x的操作的时候， 最后结果肯定有如下两个特征：
① 这个结果只有一位值是1， 其他位均是0
② 这个值的末位0的个数与原值保持一致
“当一个偶数与它的负值相与时， 结果是能整除这个偶数的最大的2的幂, 即： m = n & -n , 则 n % m = 0, 且 m = 2 ^ k”
x为奇数
奇数取反后的值一定是偶数， 而偶数的值 + 1之后， 并不会影响进位
所以进行x&-x后，剩下刚加上的那最后一位1
结论：“如果是x是奇数， 那x & -x 的结果一定是1”
最终结论
“当一个数与其取负后的值相与， 如果这个数是偶数， 则结果是能整除这个偶数的最大的2的幂(即： m = n & -n , 则 n % m = 0, 且 m = 2 ^ k)， 如果这个数是奇数， 则结果必为1”
用途： 一般可以用来获取某个二进制数的LowBit
lowbit ( n ) 定义为非负整数 n 在二进制表示下 “ 最低位的 1 及其后面的所有的 0 ” 的二进制构成的数值。
int lowbit(int x)
{
return x&(-x);
}
8.位运算（与，或，非，异或）
①与运算：运算符号为 & ，运算法则为遇0得0。也就是说只要有0，结果即为0。
举例：1001 & 1100
1 0 0 1
&
1 1 0 0
————
1 0 0 0
妙用（x&1）可以用来判断二进制数x最后一位是不是1，是1就为1，不是1则为0；
可以用来快速判断奇偶数。
②或运算：运算符号为 | ，就是一个竖线，运算法则为遇1得1。也就是说，只要有1，结果就为1。
举例：1100 | 1010
1 1 0 0
|
1 0 1 0
————
1 1 1 0
③非运算：预算符号为 ~，就是一个波浪线，运算法则为按位取反，也就是遇1取0,遇0取1，即 ~1 = 0 , ~0 = 1;
举例： ~1001
1 0 1 1
~
————
0 1 0 0
④异或运算：运算符号为 ^，就是一个乘方符号，运算法则为相同取0，不同取1。异或运算，关键在异上面，异为1，否则为0
举例：1001 ^ 1001
1 0 1 1
^
1 0 0 1
————
0 0 1 0
⑤左移与右移
<<左移
很简单的来说就是把当前的二进制，整体往左边移动N个单位，N取决于你的表达式。
例如：32 << 1 = 64。
>>右移
很简单的来说，把当前的二进制，整体往右边移动N的单位，得到一个新的二进制。
例如：32 >> 1 = 16
//用二进制数来表示信号灯的7个灯管，用异或运算来模拟灯管的变化
#include <stdio.h>
#include <string.h>
const int N = 1e5 + 1;
int check(int x)
{
int num=0;
while(x)
{
num += (x & 1);
x = x >> 1;
}
return num;
}
int main()
{
//abcdefg
int pos[] = {
0B1111110,
0B0110000,
0B1101101,
0B1111001,
0B0110011,
0B1011011,
0B1011111,
0B1110000,
0B1111111,
0B1111011 };
int i, len;
int ans = 0;
char s[N], t[N];
scanf("%s", s);
scanf("%s", t);
len = strlen(s);
for(i=0;i<len;i++)
{
ans += check(pos[s[i] - '0'] ^ pos[t[i] - '0']);
}
printf("%d", ans);
return 0；
}
