位运算基础

位运算基础

作者：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;
}

应用：0二进制问题 - 蓝桥云课 (lanqiao.cn)

虽然有一半的测试数据会超时，但是强在代码容易写，而且不用思考，先拿一半分数再说

#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()
{	//abcdefgint 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；
}