#创作计划# 位运算详解

yaonainai

2025-09-14 20:34:11

发布于：浙江

11阅读

0回复

0点赞

0.前言

位运算是 $OI$ 之路上的一大重要考点，这是一篇详细讲解位运算的帖子。

注意：以下操作符均针对整数的二进制位。

运算符	名称	描述	示例（以 4-bit 为例）
`&`	与	两位都为 1 时，结果才为 1	`1010 & 1100 = 1000`
`\|`	或	两位都为 0 时，结果才为 0	`1010 \| 1100 = 1110`
`^`	异或	两位相同时为 0，不同时为 1 重要性质： `x ^ x = 0`, `x ^ 0 = x`	`1010 ^ 1100 = 0110`
`~`	取反	一元运算符，0 变 1，1 变 0	`~1010 = 0101` (结果取决于位数)
`<<`	左移	将二进制位全部左移若干位，高位丢弃，低位补 0	`1010 << 2 = 1000` (相当于乘以 4)
`>>`	右移	将二进制位全部右移若干位。无符号数：高位补 0。有符号数：高位补符号位（算术右移）	`1010 >> 2 = 0010` `1110 >> 2 = 1111`

判断奇偶性
x & 1 结果为 1 则是奇数，为 0 则是偶数。
- 原理：二进制最后一位为 1 则是奇数。
取二进制的最右边的 1（lowbit）
x & (-x)
- 原理：-x 是 x 的补码，等于 ~x + 1。此操作会将 x 最右边的 1 保留，其余位置全部置 0。
- 示例：x = 12 (1100)， -x = -12 (0100)， 1100 & 0100 = 0100。
消除二进制的最右边的 1
x & (x - 1)
- 原理：x-1 会将最右边的 1 变成 0，并将其后的 0 都变成 1。与原数进行与操作后，原数最右边的 1 及其后面的位都变成 0。
- 示例：x = 12 (1100)， x-1 = 11 (1011)， 1100 & 1011 = 1000。
- 应用：统计二进制中 1 的个数、判断一个数是否是 2 的幂。
异或的巧妙应用
- 交换两个数：a ^= b; b ^= a; a ^= b;
- 寻找只出现一次的数字：a ^ a = 0， a ^ 0 = a。对所有数进行异或，成对的数会抵消为 0，最后的结果就是那个只出现一次的数。

@AC君请求加精

有帮助，赞一个

去预览

0/2000

这里空空如也