有必要学习掌握一下位运算的知识点！！灵神位运算题单:

• 分享｜从集合论到位运算，常见位运算技巧分类总结！

一、位运算

1.1、按位与（AND， x & y）

按位与，只有两个都位1的时候，结果才为1，（x & y）

x	y	x & y
0	0	0
0	1	0
1	0	0
1	1	1

1.2、按位或（OR， x | y）

只要有一个1，结果就为1，（x | y）

x	y	x | y
0	0	0
0	1	1
1	0	1
1	1	1

1.3、取反（NOT，~x）

取反，0变为1，1变为0

x	~x
0	1
1	0

1.4、异或（XOR，x ^ y）

异或操作是一个数学运算符，用于逻辑运算，符号为^，多数情况下使用xor表示异或。

简而言之，相同为 0， 不同为 1；【0 xor 0 = 0， 1 xor 1 = 0，0 xor 1 = 1】

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	0

异或运算法则：

• a ^ b = b ^ a
• a ^ b ^ c = a ^ (b ^ c)
• 例如：x=0101, y=1011， x^y=1110

异或的应用：

• 交换两个变量的值，除了通常使用的借用中间变量进行交换外， 还可以利用异或操作，仅适用两个变量进行交换，如：a=a^b, b=a^b, a=a^b, 完成对 a 和 b 的交换。

二、位运算操作

操作	含义	实例
x & (x-1)	清除x最低位的1，如果结果是0，那么x是0或者是2 ^ k	1101 & 1100 -> 1100
x | (x + 1)	将x最低位的0变成为1	1101 | 1110 -> 1111
x & -x	提取最低位的1	x = 1100 , -> 4
~x & (x + 1)	提取最低位的0	x = 1101, -> 2

三、集合与位运算

3.1、集合与集合

交集、并集、补集

其中 & 表示按位与，| 表示按位或， ⊕ 表示按位异或，∼ 表示按位取反。

• 按位与
• 按位或
• 对称差，{0,2,3} ⊕ {0,1,2} -> {1,3}

3.2、集合与元素

补码：在补码系统中，负数-s的表示是正数s的按位取反后加一。

s = 101100
~s = 010011
~s + 1 = 010100  // -s表示s的补码，按位取反后加一
s&(-s) = 000100

s = 101100
s-1 = 101011
s&(s-1) = 101000

集合可以用二进制表示，二进制从低到高，第i位为1表示i在集合中，为0表示i不在集合中。例如集合{0,2,3}可以用二进制1101表示；反过来，二进制1101就对应集合{0,2,3}。

• 计算二进制中1的个数，也就是集合大小
• 计算二进制的长度，减一后得到集合最大元素
• 计算二进制尾零个数，也就是集合最小元素。

调用下方函数的时间复杂度都是O(1)

// 判断最低是1的位置, 1101 -> 0, 1100 -> 2
System.out.println(Integer.numberOfTrailingZeros(12));  // 2
// 判断二进制前面有多少个0， 1101 -> 28, 1100 -> 28
System.out.println(Integer.numberOfLeadingZeros(12));

术语	Python	Java
集合大小	s.bit_count()	Integer.bitCount(s)
二进制长度	s.bit_length()	32-Integer.numberOfLeadingZeros(s)
集合最大元素	s.bit_length()-1	31-Integer.numberOfLeadingZeros(s)
集合最小元素	(s&-s).bit_length()-1	Integer.numberOfTrailingZeros(s)

3.3 、遍历集合

设元素范围从0到n-1，枚举范围中的元素i, 判断i是否在集合s中。

Java

// set {0, 2, 3}
int s = 13;
for (int i = 0; i < 10; i++) {
  // s可以表示为集合的二进制形式，所以右移 i 位，就到了第 i 位, 
  // & 1判断最后一位是否为1，如果为1则表示在集合中
    if (((s >> i) & 1) == 1) {
        System.out.println(i); // 0, 2, 3
    }
}

Python

# set {0, 2, 3}
s = 13
for i in range(n):
    if (s >> i) & 1:  # i 在 s 中
        # 处理 i 的逻辑
        print(i)  # 0, 2, 3

也可以直接遍历集合s中的元素，不断计算集合最小元素、去掉最小元素，直到集合为空。

Java

for(int t = s; t>0;t &= t-1){
  int i = Integer.numberOfTrailingZeros(t); // 返回 1 的最低位
  
  // 处理i的逻辑
}

Python

t = s
while t:
  lowbit = t & -t
  t ^= lowbit
  i = lowbit.bit_length() - 1
  # 处理i的逻辑

3.4、枚举集合

3.4.1、枚举所有集合

设元素范围从 0 到 n−1，从空集 ∅ 枚举到全集 U：

Java

// 这里n是多少？
// 就是遍历[0, n-1)
for(int s = 0; s < (1 << n);s++){
  // 处理s的逻辑
}

Python

# coding...

3.4.2、枚举非空子集

设集合为s，从大到小枚举s的所有非空子集sub：

为什么sub = (sub-1) & s?

• 暴力做法是从 s 出发，不断减一，直到 0。但这样做，中途会遇到很多并不是 s 的子集的情况。例如 s=10101 时，减一得到 10100，这是 s 的子集。但再减一就得到 10011 了，这并不是 s 的子集，下一个子集应该是 10001。

如何快速跳到下一个子集呢？比如，怎么从 10100 跳到 10001？

• 普通的二进制减法，是 10100−1=10011，也就是把最低位的 1 变成 0，同时把最低位的 1 右边的 0 都变成 1。 压缩版的二进制减法也是类似的，对于 10100→10001，也会把最低位的 1 变成 0，对于最低位的 1 右边的 0，并不是都变成 1，只有在 s=10101 中的 1 才会变成 1。怎么做到？减一后 & 10101 就行，也就是 (10100−1) & 10101=10001。

Java

int s = 13; // 1101
// 为什么要(sub-1) & s ? 将sub转化成下一个数
for (int sub = s; sub > 0; sub = (sub - 1) & s) {
    // 1101
    // 13, 12, 9, 8, 5, 4, 1
    // 1101, 1100, 1001, 1000, 0101, 0100, 0001
    System.out.println(sub);
}

Python

sub = s
while sub:
  # 处理 sub 的逻辑
  sub = (sub-1) & s

3.4.3、枚举子集（包含空集）

如果要从大到小枚举s的所有子集sub（从s枚举到空集），可以这样写：

其中 Java 和 C++ 的原理是，当 sub=0 时（空集），再减一就得到 −1，对应的二进制为 111⋯1，再 &s 就得到了 s。所以当循环到 sub=s 时，说明最后一次循环的 sub=0（空集），s 的所有子集都枚举到了，退出循环。

Java

int s = 13; // 1101
int sub = s;
do {
    // 处理sub的逻辑
    // 13, 12, 9, 8, 5, 4, 1, 0
    System.out.println(sub);
    sub = (sub - 1) & s;
} while (sub != s);

Python

sub = s
while True:
  # 处理 sub 逻辑
  if sub == 0:
    break
 	sub = (sub - 1) & s  # 保证只有s中有的1为1

Changelog

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25