C# 位运算：异或、popcount 与子集枚举

发布于 2026年9月14日

用异或找出只出现一次的值，用上大多数 C# 代码从没碰过的 BitOperations 类，再看看移位次数被悄悄取模、结果什么都没移的那个坑。

从第 3 篇开始，这个系列就一直在用位运算，只是没明说。前缀异或是模式 15，状态压缩 DP 是模式 45，第 15 篇的子集是靠一个计数器生成的。这一篇补上剩下的内容，以及 C# 特有的坑。

下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴过来。

模式 76 — 用异或找出只出现一次的值

除了一个值，其余每个值都出现两次。用 O(1) 内存找出那个值。

起作用的是三条性质：x ^ x == 0、x ^ 0 == x，以及顺序无关。任何出现偶数次的值都会消失，不管它在输入里的哪个位置。

int[] a = [4, 1, 2, 1, 2];

// XOR has three properties and all three are needed:
//   x ^ x == 0      a pair cancels
//   x ^ 0 == x      zero is the identity
//   order does not matter (commutative and associative)
int unique = 0;
foreach (int x in a)
{
    int before = unique;
    unique ^= x;
    Console.WriteLine($"{before,3} ^ {x} = {unique,3}");
}

Console.WriteLine($"\nthe value appearing once: {unique}");
Console.WriteLine($"\nBecause order does not matter, this is the same as");
Console.WriteLine($"(1^1) ^ (2^2) ^ 4  =  0 ^ 0 ^ 4  =  4, whatever order they arrived in.");

// The same idea finds a missing number in 0..n without any arithmetic.
int[] present = [0, 1, 3];
int n = 3;
int missing = n;
for (int i = 0; i < n; i++) missing ^= i ^ present[i];
Console.WriteLine($"\nmissing from [{string.Join(",", present)}] out of 0..{n}: {missing}");
Console.WriteLine("No sum, so nothing can overflow — which the sum formula can.");

输出：

  0 ^ 4 =   4
  4 ^ 1 =   5
  5 ^ 2 =   7
  7 ^ 1 =   6
  6 ^ 2 =   4

the value appearing once: 4

Because order does not matter, this is the same as
(1^1) ^ (2^2) ^ 4  =  0 ^ 0 ^ 4  =  4, whatever order they arrived in.

missing from [0,1,3] out of 0..3: 2
No sum, so nothing can overflow — which the sum formula can.

三条性质，缺一不可：x ^ x == 0、x ^ 0 == x，以及顺序无关。所以每个重复的值，不管两份拷贝在哪里，都会自己抵消掉，最后剩下的就是那个没有配对的值。

找缺失数字的变体也值得掌握。常见解法是 n(n+1)/2 - sum，平时没问题，可一旦 n 大到让求和溢出就不行了，这就是第 10 篇讲过的那个坑。异或没有这个问题，因为数值从来不会变大。

代价： O(n) 时间，O(1) 空间。

适用场景： 东西两两配对，只有一个落单：缺失的元素、唯一没有配对的值、找重复项。

模式 77 — 有两个值只出现一次

同样的设定，只是落单的值变成了两个。现在把所有值异或起来，得到的是 a ^ b，不是答案，还需要再多一个想法。

两个只出现一次的值在选中的那一位上不同，所以一定会落进不同的组。每组就退化成模式 76 里只有一个落单值的问题。

int[] a = [1, 2, 1, 3, 2, 5];       // 3 and 5 appear once, the rest twice

// XOR everything: the pairs cancel and what is left is a ^ b.
int both = 0;
foreach (int x in a) both ^= x;
Console.WriteLine($"xor of everything = {both}  (= a ^ b, binary {Convert.ToString(both, 2)})");

// A set bit in a ^ b is a position where a and b DIFFER. Take the lowest one.
int bit = both & -both;             // two's complement: isolates the lowest set bit
Console.WriteLine($"lowest set bit    = {bit}  (binary {Convert.ToString(bit, 2)})");
Console.WriteLine($"  because -x is ~x + 1, so x & -x keeps exactly that bit");

// Split into two groups by that bit. The two uniques cannot land together.
int groupOn = 0, groupOff = 0;
foreach (int x in a)
{
    if ((x & bit) != 0) groupOn ^= x; else groupOff ^= x;
}

Console.WriteLine($"\ngroup with the bit set   -> xor = {groupOn}");
Console.WriteLine($"group with it clear      -> xor = {groupOff}");
Console.WriteLine($"\nthe two values appearing once: {Math.Min(groupOn, groupOff)} and {Math.Max(groupOn, groupOff)}");
Console.WriteLine($"\nEvery duplicate pair has the same bit, so both copies land in the same");
Console.WriteLine($"group and cancel. The two uniques differ at that bit, so they separate.");

输出：

xor of everything = 6  (= a ^ b, binary 110)
lowest set bit    = 2  (binary 10)
  because -x is ~x + 1, so x & -x keeps exactly that bit

group with the bit set   -> xor = 3
group with it clear      -> xor = 5

the two values appearing once: 3 and 5

Every duplicate pair has the same bit, so both copies land in the same
group and cancel. The two uniques differ at that bit, so they separate.

a ^ b 中为 1 的位，就是两个值不同的位置。随便挑一位（最低位最方便），按它把输入分成两组。

重复值的两份拷贝每一位都一样，所以总在同一侧，每一对都在组内抵消。两个唯一值在这一位上不同，所以分落两侧。这样每组恰好只有一个落单值，又回到了模式 76。

both & -both 取出最低的那个 1。为什么行得通，见模式 80。

代价： O(n) 时间，O(1) 空间，扫两趟。

适用场景： 恰好有两个东西没有配对。“按不同的位拆分”这个思路还能继续推广，但那时就不再是简短的解法了。

模式 78 — `BitOperations` 与位计数

System.Numerics.BitOperations 从 .NET Core 3.0 起就有了，大多数 C# 代码却从没用过。在硬件支持的地方，它的每个方法都编译成一条 CPU 指令。

using System.Numerics;

// System.Numerics.BitOperations maps to a single CPU instruction where one
// exists. Hand-rolled loops are strictly worse and much longer.
foreach (uint x in new uint[] { 0, 1, 7, 8, 255, 1024 })
    Console.WriteLine($"{x,5}  popcount {BitOperations.PopCount(x),2}   " +
                      $"leadingZeros {BitOperations.LeadingZeroCount(x),2}   " +
                      $"trailingZeros {BitOperations.TrailingZeroCount(x),2}   " +
                      $"isPow2 {BitOperations.IsPow2(x),-5}  log2 {(x == 0 ? "-" : BitOperations.Log2(x).ToString())}");

Console.WriteLine();
Console.WriteLine($"RoundUpToPowerOf2(100) = {BitOperations.RoundUpToPowerOf2(100)}");
Console.WriteLine($"RoundUpToPowerOf2(128) = {BitOperations.RoundUpToPowerOf2(128)}");

// Counting bits for 0..n, without calling popcount at all.
// i >> 1 is i with the last bit dropped, and its answer is already known.
int n = 8;
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);

Console.WriteLine($"\ncounting bits 0..{n} by DP: [{string.Join(", ", bits)}]");
Console.WriteLine($"cross-check with PopCount: [{string.Join(", ", Enumerable.Range(0, n + 1).Select(i => BitOperations.PopCount((uint)i)))}]");

// Brian Kernighan: x & (x - 1) clears the lowest set bit, so the loop runs
// once per SET bit rather than once per bit position.
static int CountSlow(uint x) { int c = 0; while (x != 0) { x &= x - 1; c++; } return c; }
Console.WriteLine($"\nKernighan on 1024 (one set bit): {CountSlow(1024)} iteration, not 32");

输出：

    0  popcount  0   leadingZeros 32   trailingZeros 32   isPow2 False  log2 -
    1  popcount  1   leadingZeros 31   trailingZeros  0   isPow2 True   log2 0
    7  popcount  3   leadingZeros 29   trailingZeros  0   isPow2 False  log2 2
    8  popcount  1   leadingZeros 28   trailingZeros  3   isPow2 True   log2 3
  255  popcount  8   leadingZeros 24   trailingZeros  0   isPow2 False  log2 7
 1024  popcount  1   leadingZeros 21   trailingZeros 10   isPow2 True   log2 10

RoundUpToPowerOf2(100) = 128
RoundUpToPowerOf2(128) = 128

counting bits 0..8 by DP: [0, 1, 1, 2, 1, 2, 2, 3, 1]
cross-check with PopCount: [0, 1, 1, 2, 1, 2, 2, 3, 1]

Kernighan on 1024 (one set bit): 1 iteration, not 32

PopCount、LeadingZeroCount、TrailingZeroCount、Log2、IsPow2 和 RoundUpToPowerOf2 加起来，能替代大量手写的位操作代码。注意它们接受的是无符号类型。

计数的 DP 值得单独看一看。bits[i] = bits[i >> 1] + (i & 1) 的意思是：i >> 1 就是去掉最后一位的 i，这个数更小，答案已经算好了。扫一遍数组，完全不用 popcount。

还有 Brian Kernighan 的技巧：x &= x - 1 清掉最低的那个 1，于是循环按为 1 的位来跑，而不是按每个位的位置跑。对 1024 来说，只跑一次，而不是三十二次。

适用场景： 统计或定位二进制位。写循环之前，先查查 BitOperations。

模式 79 — 枚举子掩码

给定一组位，访问它的每一个子集，并且不碰这组位以外的任何位。

using System.Numerics;

int mask = 0b1011;      // elements 0, 1 and 3 are in the set

Console.WriteLine($"mask = {Convert.ToString(mask, 2).PadLeft(4, '0')}\n");

// Walk only the SET bits, not all 32 positions.
Console.WriteLine("set bits:");
for (int m = mask; m != 0; m &= m - 1)
{
    int low = m & -m;                       // lowest set bit
    Console.WriteLine($"  bit {BitOperations.Log2((uint)low)}   ({Convert.ToString(low, 2).PadLeft(4, '0')})");
}

// Every SUBSET of the set bits, without touching any bit outside the mask.
Console.WriteLine("\nevery submask:");
int count = 0;
for (int s = mask; ; s = (s - 1) & mask)
{
    Console.WriteLine($"  {Convert.ToString(s, 2).PadLeft(4, '0')}   " +
                      $"[{string.Join(",", Enumerable.Range(0, 4).Where(i => (s & (1 << i)) != 0))}]");
    count++;
    if (s == 0) break;                      // 0 must be emitted, then stop
}

Console.WriteLine($"\n{count} submasks, expected 2^{BitOperations.PopCount((uint)mask)} = {1 << BitOperations.PopCount((uint)mask)}");
Console.WriteLine();
Console.WriteLine("(s - 1) borrows through the low zero bits; & mask puts back only the");
Console.WriteLine("bits that belong to the set. It walks the submasks in descending order");
Console.WriteLine("and touches each exactly once.");
Console.WriteLine();
Console.WriteLine("Over ALL masks this is 3^n total work, not 4^n — each element is either");
Console.WriteLine("out of the mask, in the mask but not the submask, or in both.");

输出：

mask = 1011

set bits:
  bit 0   (0001)
  bit 1   (0010)
  bit 3   (1000)

every submask:
  1011   [0,1,3]
  1010   [1,3]
  1001   [0,3]
  1000   [3]
  0011   [0,1]
  0010   [1]
  0001   [0]
  0000   []

8 submasks, expected 2^3 = 8

(s - 1) borrows through the low zero bits; & mask puts back only the
bits that belong to the set. It walks the submasks in descending order
and touches each exactly once.

Over ALL masks this is 3^n total work, not 4^n — each element is either
out of the mask, in the mask but not the submask, or in both.

有两个循环值得背下来。

for (int m = mask; m != 0; m &= m - 1) 遍历为 1 的位，每位一次，空位直接跳过。

for (int s = mask; ; s = (s - 1) & mask) 遍历子掩码。减一会向低位的 0 一路借位；& mask 只把属于集合的位放回来。它按降序遍历，每个子掩码恰好访问一次。

这个循环的形状不常见，是有意为之。0 是合法的子掩码，必须输出，但 (0 - 1) & mask 又变回 mask，循环会无限重来。放在底部的 if (s == 0) break; 保证先输出 0，再停下。

复杂度这个结论才是它重要的原因。对每个掩码枚举它的所有子掩码，总共是 3ⁿ，不是 4ⁿ，因为每个元素只有三种状态：不在掩码里、在掩码里但不在子掩码里、两者都在。正因如此，n = 20 时对所有划分做子集和 DP 才跑得动。

适用场景： 状态压缩 DP 需要考虑把一个集合拆开的各种方式：分配问题、分组问题、覆盖问题。

模式 80 — C# 位运算的坑

四个坑，都源于 C# 的 int 是有符号的。

这就是 x & -x 行得通的原因，它依赖补码。上面的模式 77 用到了它，树状数组（Fenwick 树）遍历索引也靠它。

// 1. The shift COUNT is masked. For int it is taken modulo 32.
Console.WriteLine($"1 << 31 = {1 << 31}");
Console.WriteLine($"1 << 32 = {1 << 32}   <- not 0, and not 4294967296: the count wrapped to 0");
Console.WriteLine($"1 << 33 = {1 << 33}   <- same as 1 << 1");
Console.WriteLine($"1L << 32 = {1L << 32}   <- long shifts are taken modulo 64");
Console.WriteLine();
Console.WriteLine("So a bitmask over more than 31 items MUST use long, and the failure is");
Console.WriteLine("silent — 1 << 32 is a perfectly ordinary 1.");

// 2. >> keeps the sign. >>> does not. (>>> is C# 11 and later.)
Console.WriteLine();
int neg = -8;
Console.WriteLine($"-8  >>  1 = {neg >> 1,12}   arithmetic shift, sign extends");
Console.WriteLine($"-8  >>> 1 = {neg >>> 1,12}   unsigned shift, zeros shifted in");
Console.WriteLine($"int.MinValue >> 31 = {int.MinValue >> 31,4}   all sign bits");
Console.WriteLine($"int.MinValue >>> 31 = {int.MinValue >>> 31,3}   just the top bit");

// 3. Which is why popcount loops need uint, or they never terminate.
Console.WriteLine();
static int Wrong(int x) { int c = 0; int guard = 0; while (x != 0 && guard++ < 40) { c += x & 1; x >>= 1; } return guard >= 40 ? -1 : c; }
static int Right(int x) { int c = 0; uint u = (uint)x; while (u != 0) { c += (int)(u & 1); u >>= 1; } return c; }
Console.WriteLine($"counting bits of -8 with int  >>: {Wrong(-8)}   (-1 means it never terminated)");
Console.WriteLine($"counting bits of -8 with uint >>: {Right(-8)}");

// 4. -x is ~x + 1, which is what makes x & -x work.
Console.WriteLine();
int v = 12;   // 1100
Console.WriteLine($"v      = {Convert.ToString(v, 2).PadLeft(8, '0')}");
Console.WriteLine($"~v     = {Convert.ToString(~v & 0xFF, 2).PadLeft(8, '0')}");
Console.WriteLine($"-v     = {Convert.ToString(-v & 0xFF, 2).PadLeft(8, '0')}   (= ~v + 1)");
Console.WriteLine($"v & -v = {Convert.ToString(v & -v, 2).PadLeft(8, '0')}   the lowest set bit, on its own");

输出：

1 << 31 = -2147483648
1 << 32 = 1   <- not 0, and not 4294967296: the count wrapped to 0
1 << 33 = 2   <- same as 1 << 1
1L << 32 = 4294967296   <- long shifts are taken modulo 64

So a bitmask over more than 31 items MUST use long, and the failure is
silent — 1 << 32 is a perfectly ordinary 1.

-8  >>  1 =           -4   arithmetic shift, sign extends
-8  >>> 1 =   2147483644   unsigned shift, zeros shifted in
int.MinValue >> 31 =   -1   all sign bits
int.MinValue >>> 31 =   1   just the top bit

counting bits of -8 with int  >>: -1   (-1 means it never terminated)
counting bits of -8 with uint >>: 29

v      = 00001100
~v     = 11110011
-v     = 11110100   (= ~v + 1)
v & -v = 00000100   the lowest set bit, on its own

移位次数会被掩码截断。 对 int 来说，移位次数对 32 取模，所以 1 << 32 是 1，不是 0，也不是 4294967296。超过 31 个元素的位掩码必须用 long；用错了不会抛异常，结果看起来也只是个普通的值。

>> 保留符号，>>> 不保留。 -8 >> 1 是 -4，做算术时通常正合你意，做位操作时却从来不是你想要的。C# 11 加入了无符号版本 >>>。

对负的 int 做 popcount 循环，永远停不下来。 对负数执行 x >>= 1，高位一直补进符号位，x 永远到不了 0。上面的程序得加一个保护计数才能安全地演示这一点。先转成 uint。

-x 就是 ~x + 1。 进位穿过末尾的 0 一路向上，停在最低的那个 1，那是 x 和 -x 唯一仍然一致的位置。这就是 x & -x 行得通的全部原因，树状数组遍历索引靠的也是它。

要点

异或会抵消成对的值，与顺序无关。 一趟扫描，不占额外内存，也没有求和那样可能溢出的算术。
a ^ b 中为 1 的位，就是两者不同的地方。 按这一位拆分，两个落单值就变成两个各有一个落单值的独立问题。
写位循环之前，先查 BitOperations。 PopCount、TrailingZeroCount、Log2、IsPow2 都是单条指令，而且接受无符号类型。
bits[i] = bits[i >> 1] + (i & 1)。 统计一整段范围内每个数的 1 的个数，完全不需要 popcount。
x &= x - 1 清掉最低的那个 1，所以循环按为 1 的位跑，而不是按每个位置跑。
(s - 1) & mask 遍历子掩码，break 必须放在底部，这样 0 才会在循环重来之前被输出。
1 << 32 是 1。 移位次数对 int 截断为低 5 位，对 long 截断为低 6 位。超过 31 个标志就用 long。
在循环里右移之前先转成 uint，否则负数会一直补进符号位，永远停不下来。

八十个模式

十六篇。第 1 到 10 篇是竞赛内容：数组、图、动态规划，还有决定这一切能否在时限内跑完的 C# I/O。第 11 到 16 篇是面试内容：链表、树、区间、回溯和位运算。

拿来对照的那几份题单，加起来一共列出二十六种不同的模式。这二十六种这里全都有，另外还有五十四种。

这些东西拿来死记没多大价值。真正有用的是认出题目的形状：最小化最大值意味着二分答案，取值从 1 到 n 意味着数组本身就能当哈希表，恰好 K 个意味着算两次“至多”再相减，贪心要考虑怎么把东西塞进去时，按结束点排序而不是按起点。

这个系列里的每个程序在发布前都在 .NET 10 上跑过，每一页上的每一段输出都是它实际打印出来的结果。

这篇文章对你有帮助吗？

点一颗爱心来评分！

平均评分 0 / 5. 投票总数： 0

还没有人投票。来做第一个评分的人吧。