位运算及其对程序的优化

位运算及其对程序的优化常州市第一中学 戴涵俊JSOI2025 省队论文目 录序言 ………………………………………………………………………… 3 正文 ………………………………………………………………………… 4一、位运算的基本操作 ………………………………………………… 4 1.位运算介绍 2.位运算的优先级 3.位运算的口诀二、位运算的有用技巧 ………………………………………………… 5 1.对于 mod 运算的优化 2.位运算的一些技术 三、位运算对一些数据结构的优化 …………………………………… 6 1.循环队列 2.树状数组 3.集合 4.哈希表四、位运算对一些算法的优化 ………………………………………… 12 1.状态压缩动态规划 2.搜索五、总结 ………………………………………………………………… 15六、附录 ………………………………………………………………… 15七、参考资料 …………………………………………………………… 24 序 言 程序中所有的数据在计算机内存中都是以二进制的形式储存的。位运算，本质上就是直接对整数在内存中的二进制位进行运算，同时，数的各个二进制位互不影响。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。另外，位运算还有很多特别的技巧，能够帮助我们简化代码、美化程序等等。本文就结合自己的学习和应用经验，介绍一些位运算及其对程序的优化方法。正 文一．位运算的基本操作1. 位运算介绍① andXYX and Y000100010111 通过上表不难发现，只有当 x 和 y 都为 1 时 and 后值才为 1。and 运算主要是用来取出某个二进制位。例如：A and (1 shl 5)就是取出 A 的二进制数从右往左第 6 位。② orXYX and Y000101011111 or 运算通常用来强行给二进制的某一位赋值，注意 or 运算可能导致变量越界，对于有符号类型，or 可能把符号位取反，无符号类型可能直接就变成 0 了，这有可能会导致数据的丢失，使得程序崩溃。因此，执行 or 运算，应该尽量保证变量不超界，或者更保险地，是非负数。③xorXYX and Y000101011110 当两个位不同时得到 1，否则为 0。因此 xor 通常可以用来取反。有意思的是 xor 的逆运算是其本身。于是，我想起了一道做过的有点诡异的题目：给你 n 个数，n 大到只保证你读入不超时，其中仅有一个数出现了奇数次，要你找出...