牢记常用位运算

在计算机内部都是使用0和1这样二进制来进行存储数据，那么对于很多操作，我们可以通过相关位运算来进行实现，这里就位运算的相关技巧进行一个总结

基本原理

• $x \ ^{\land} \ 00000000 = x , x \ \& \ 00000000 = 0 , x\ |\ 00000000 = x$
• $x \ ^{\land} \ 11111111 = \sim x , x \ \& \ 11111111 = x , x\ |\ 11111111 = 11111111$
• $x \ ^{\land} \ x = 0 , x \ \&\ x = x , x\ |\ x = x$
• $>> n$为算术右移，相当于除以$2n$，例如$-7 >> 2 = -2$
• $>>>n$ 为无符号右移，左边会补上 $0$，例如 $-7 >>> 2 = 1073741822$
• $<< n$ 为算术左移，相当于乘以$2n$，例如$-7 << 2 = -28$

运算技巧

根据这些特点，部分操作就显得非常容易

• $^{\land}$实现数位翻转：$x \ ^{\land} \ 11111111 = \sim x$
• 三个数中重复的两个数去除，只留下另一个数：利用$x \ ^{\land} \ 00000000 = x, x \ ^{\land} \ x = 0$
• $\&$实现掩码操作：一个数$num$与$mask:00111100$进行位与操作，只保留$num$中与$mask$的$1$部分相对应的位
• $|$实现设值操作：一个数$num$与$mask:00111100$进行位或操作，将$num$中与$mask$的$1$部分相对应的位都设置为$1$
• $n\ \&\ (n - 1)$去除$n$的位级中最低的那一位$1$，例如对于二进制表示$01011011$，减去$1$得到$01011010$，这两个数相与得到$01011010$
• $-n = \sim n + 1$
• $n\ \&\ (-n)$：得到$n$的位级表示中最低的那一位$1$

求第k位数

例如：$n = 15 = (1111)_{2}$

• 先把第$k$位移到最后一位：$x = n >> k$
• 看最后一位是多少：$x\ \& \ 1$
• 因此要取最后一位元素：$x = n >> k\ \& \ 1$

#include <iostream>

using namespace std;

int main() {
    int n = 10;
    // 从最高位输出：就是输出其二进制表示
    for (int k = 3; k >= 0; k--)
        cout << (n >> k & 1);
   	return 0;
}

lowbit(x)

• $lowbit(x)$：返回$x$的最后一位$1$，$x = 1010, lowbit(x) = 10, x = 101000, lowbit(x) = 1000$

• $-x = \sim x + 1$

• 有了$lowbit(x)$操作，那么计算$x$中有多少位$1$就显得非常容易

#include <iostream>

using namespace std;

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

int main() {
    int x, ans = 0;
    scanf("%d", &x);
    while (x) {
        x -= lowbit(x);
        ans++;
    }
    printf("%d ", ans);
    return 0;
}