位运算性质&&应用 &&||^~
2026-07-22 18:38:13
发布于：浙江
位运算
- 基础运算符
1.1 与运算（&）
含义：对应位都为 1 时结果位为 1，否则为 0
例：
6=110
2
, 5=101
2
6 & 5=100
2
=4
1.2 或运算（|）
含义：对应位只要有一个为 1，结果位为 1
例：
6=110
2
, 5=101
2
6 ∣ 5=111
2
=7
1.3 取反运算（~)
含义：0↔1（对所有位取反）
例：
5=00000101
2
∼5=11111010
2
（在常见补码表示下，这个结果对应十进制 −6）
1.4 异或运算（^）
含义：对应位不同为 1，相同为 0
例：
6=110
2
, 5=101
2
6
^
5=011
2
=3
2. 移位运算符
2.1 左移（<<）
含义：整体向左移动，低位补 0
直观效果：相当于乘以 2
k
例：
3=00000011
2
3≪2=00001100
2
=12
2.2 右移（>>）
含义：整体向右移动，低位被舍弃
直观效果：相当于除以 2
k
并向下取整
例：
13=00001101
2
13≫2=00000011
2
=3
3. 位运算性质
3.1 异或性质（^）
交换律、结合律成立
自反：a⊕a=0
与 0 的关系：a⊕0=a
可逆性：(a⊕b)⊕b=a
3.2 与性质（&）
交换律、结合律成立
幂等：a & a=a
吸收：a & 0=0，a & 全1=a
递减：a & b≤min(a,b)
3.3 或性质（|）
交换律、结合律成立
幂等：a∣a=a
吸收：a∣0=a，a∣全1=全1
递增：a∣b≥max(a,b)
4. 位运算技巧
4.1 判断某一位是否为 1
思路：构造掩码 mask=1≪k，用与运算判断第 k 位是否为 1
表达式：x & (1≪k)
例：
x=13=1101
2
判断第 2 位：mask=0100
2
1101
2
& 0100
2
=0100
2
=0，所以第 2 位是 1
判断第 1 位：mask=0010
2
1101
2
& 0010
2
=0000
2
=0，所以第 1 位是 0
4.2 将某一位置 1 / 置 0 / 翻转
置 1：x ∣= (1≪k)
置 0：x &= ∼(1≪k)
翻转：x
^
= (1≪k)
例：x=10=1010
2
(1) 置第 0 位为 1
k=0，1≪0=0001
2
x
′
=x ∣ (1≪0)
=1010
2
∣ 0001
2
=1011
2
=11
(2) 置第 1 位为 0
k=1，1≪1=0010
2
，∼(1≪1)=∼0010
2
=1101
2
x
′
=x & ∼(1≪1)
=1010
2
& 1101
2
=1000
2
=8
(3) 翻转第 3 位（0↔1）
k=3，1≪3=1000
2
x
′
=x
^
(1≪3)
=1010
2
^
1000
2
=0010
2
=2
4.3 找最低位的 1（lowbit）与删除最低位的 1
lowbit：lowbit(x)=x & (−x)（提取最低位的 1 所代表的值）
删除最低位的 1：x & (x−1)
例：
x=12=1100
2
lowbit(x)=0100
2
(=4)
x & (x−1)=1100
2
& 1011
2
=1000
2
(=8)
4.4 统计二进制中 1 的个数
方法：不断删除最低位的 1，删除次数就是 1 的个数
操作：反复执行 x &= (x−1)
例：
x=13=1101
2
1101→1100→1000→0000
共 3 次，所以 popcount(13)=3
4.5 判断是否为 2 的幂
结论：对 x>0，若 x & (x−1)=0，则 x 是 2 的幂
（2 的幂在二进制中只有一个 1）
例：
8=1000
2
：8−1=7=0111
2
，1000
2
& 0111
2
=0000
2
，是 2 的幂
12=1100
2
：12−1=11=1011
2
，1100
2
& 1011
2
=1000
2
=0，不是 2 的幂
4.6 用整数的二进制位表示集合及子集枚举
集合表示（状态压缩）：用一个整数 mask 表示集合
第 i 位为 1：元素 i 在集合中
第 i 位为 0：元素 i 不在集合中
例：
有 4 个元素 {0,1,2,3}，mask=13=1101
2
表示集合为 {0,2,3}（第 0,2,3 位为 1）
ex 子集枚举 / 超集枚举
设全集大小为 n，全集掩码 U=(1≪n)−1。
- 子集枚举（枚举 mask 的所有子集 sub）
for (int sub = mask; ; sub = (sub - 1) & mask) {
if (sub == 0) break;
} - 超集枚举（枚举所有 sup⊇mask）
做法：先枚举可选位 free=U⊕mask 的子集 t，再令 sup=mask∣t。
int free = U ^ mask;
for (int t = free; ; t = (t - 1) & free) {
int sup = mask | t;
if (t == 0) break;
}
5. 常用函数
5.1 统计二进制中 1 的个数（popcount）
__builtin_popcount(x)
__builtin_popcountll(x)
5.2 末尾连续 0 的个数（ctz）
__builtin_ctz(x)
__builtin_ctzll(x)
注意：当 x=0 时结果未定义（调用前需保证 x
=0）
5.3 前导连续 0 的个数（clz）
__builtin_clz(x)
__builtin_clzll(x)
注意：当 x=0 时结果未定义（调用前需保证 x
=0）
5.4 最高位 1 的位置（0-based）
对 x>0：
pos = 31 - __builtin_clz(x)（32 位）
pos = 63 - __builtin_clzll(x)（64 位）
5.5 最低位 1 的位置（0-based）
对 x>0：
pos = __builtin_ctz(x)（32 位）
pos = __builtin_ctzll(x)（64 位）
【前置知识点】
这里空空如也
有帮助，赞一个