NOIP中的数学第1课位运算

位运算常用运算

位操作是一种速度非常快的基本运算&＃xff1a;有左移、右移、与、或、非、异或等运算。

左移&＃xff1a;左移一位&＃xff0c;相当于某数乘以2&＃xff0c;比如110左移1位变为1100 &＃xff0c;右边的空位补0&＃xff0c;6变为12&＃xff0c;表示为(110<<1)
因此左移x位&＃xff0c;相当于该数乘以2^x

在右移时&＃xff0c;需要注意符号位问题。对无符号数&＃xff0c;右移时左边高位移入0。对于有符号的值&＃xff0c;如果原来符号位为0&＃xff08;该数为正&＃xff09;&＃xff0c;则左边也是移入0&＃xff0c;如果上例表示的那样&＃xff0c;如果符号位原来为 1&＃xff08;该数为 负&＃xff09;&＃xff0c;则左边移入的 0还是1&＃xff0c;要取决于所用的计算机系统。移入0 称为 逻辑右移&＃xff0c;即简单右移。移入1称为算术右移。

右移&＃xff1a;右移一位&＃xff0c;相当于某数除以2&＃xff0c;比如110右移1位变为011&＃xff0c;6变为3&＃xff0c;表示为(110>>1)
因此右移x位&＃xff0c;相当于该数除以2^x。

与运算&＃xff1a;按位进行“与”运算&＃xff0c;两数同一位都为1时结果为1&＃xff0c;否则为0。例如:101&110&＃61;100。

或运算&＃xff1a;按位进行“或”运算&＃xff0c;两数同一位都为0时结果为0&＃xff0c;否则为1。例如:101|110&＃61;11l。

非运算&＃xff1a;按位取反。例如~101&＃61;010。
“异或”运算符&＃xff08;^&＃xff09; 它的规则是&＃xff1a;若参加运算的两个二进制位值相同则为0&＃xff0c;否则为1.
常见用法&＃xff1a;反转二进制&＃xff0c;只需要将想要反转的位异或1就可以&＃xff0c; 如&＃xff1a;1010^1111&＃61;0101

位运算实用”杀招“

若当前二进制位为S&＃xff0c;对S有下列操作。

①判断第i位是否为0&＃xff1a;(S&(1<

②将第i位设置为1&＃xff1a;S|(1<

③将第i位设置为0&＃xff1a;S&~(1<

例如:S&＃61;1010101,i&＃61;5。注意二进制位从0开始计数&＃xff0c;所以i&＃61;5实际上是第6位
S&(1<
课堂练习&＃xff1a;
一个奇数次

输入一个长度为n的数组&＃xff0c;考虑所有不同的数字&＃xff0c;有且只有一个数字出现了奇数次。 比如对于1 2 3 1 2 3 1&＃xff0c;我们考虑所有不同的数字1 2 3&＃xff0c;有且只有1出现了奇数次&＃xff08;3次&＃xff09; 输出这个出现了奇数次的数字。 1 <&＃61; n <&＃61; 100000 1 <&＃61; a[i] <&＃61; 10^9
输入格式
第一行一个整数n&＃xff0c; 接下来一行n个整数&＃xff0c;表示输入的数字。
输出格式 一行一个数字&＃xff0c;表示出现了奇数次的数字。
输入样例

7
1
2
3
1
2
3
1
输出样例

1

[解题思路]
一个比较简单的思路&＃xff0c;对数组排序&＃xff0c;然后逐个统计每个数字出现的次数&＃xff0c;复杂度O&＃xff08;nlogn) 。
位运算异或^&＃xff1a; 根据 XOR运算的性质&＃xff0c;a ^ a&＃61;0 。如果某个数出现了两次&＃xff0c;那么他们 异或在一起的值恰好为0。
进一步扩展&＃xff0c;出现偶数次的数异或和也一定为0&＃xff0c;出现奇数次的数异或和一定是这个数本身。因此只要将所有数异或 在一起&＃xff0c;剩下的那个数就是出现奇数次的数。

#include using namespace std;int n;int main() {
int x;
while (~scanf("%d", &n)) { int ans &＃61; 0;
for (int i &＃61; 0; i < n; i&＃43;&＃43;) { scanf("%d", &x);
ans ^&＃61; x;
}
printf("%d\n", ans);
}
return 0;
}

更多练习

1、二进制距离之和
2、区间XOR
3、最大异或和
4、两个奇数次