位运算相关宏定义

这篇把几条常用的位运算宏（和内置函数）整理一下。我一开始总把 lowbit、popcount、clz、ctz 弄混，比赛前还得现翻头文件，后来就记了这份笔记，逐个写清用途与含义。

---

1. lowbit(x)

#define lowbit(x)  ((x) & -(x))

• 含义：取出整数 x 二进制表示中最低位的那一位所对应的值。

• 举例：

  • x = 12 （二进制 1100），lowbit(12) = 12 & -12 = 0100（即 4）。
  • x = 40 （101000），lowbit(40) = 1000（即 8）。

• 用途：

  • Fenwick 树（BIT） 中，i += lowbit(i) 或 i -= lowbit(i) 用来跳到下一个或上一个节点。
  • 在一些需要枚举子集、拆分增量的状态压缩场景，也常用它来快速 “取出” 一个子集的最低位。

---

2. popcount(x)

#define popcount(x)  __builtin_popcount(x)

• 含义：统计 x 的二进制表示里有多少个 1。

• 举例：

  • popcount(13) = __builtin_popcount(1101₂) = 3。

• 用途：

  • 快速求某个状态（用位掩码表示）里 “选了多少个元素”。
  • 求汉明重量、判断奇偶性（popcount(x) & 1）等。

如果是 long long（64 位），用 __builtin_popcountll(x)。

---

3. clz(x)

#define clz(x)  __builtin_clz(x)

• 含义：返回 x 的二进制表示中，从最高位开始连续的 0 的个数，注意它针对 32 位整数。

• 举例（以 32 位为例）：

  • x = 1 （000...0001₂），clz(1) = 31。
  • x = 8 （000...1000₂），clz(8) = 28。

• 用途：

  • 快速求最高位所在位置：int msb = 31 - clz(x);
  • 用于对数计算 ⌊log2(x)⌋、分桶、bit-DP 中确定状态位数。

__builtin_clzll(x) 可用于 64 位。

---

4. ctz(x)

#define ctz(x)  __builtin_ctz(x)

• 含义：返回 x 的二进制表示中，从最低位开始连续的 0 的个数。

• 举例：

  • x = 8 （...01000₂），ctz(8) = 3（因为最低的三个位是 0，第四位是 1）。
  • x = 12 (1100₂)，ctz(12) = 2。

• 用途：

  • 找出 lowbit(x) 对应的下标：idx = ctz(x);
  • 枚举子集/拆分子状态时，快速定位某一位。

---

小结对比

宏 / 函数	含义	应用场景
lowbit(x)	x & -x，取出最低的 1 所在的那一位的值	Fenwick 树转移、子集拆分
popcount(x)	统计 x 中有多少个 1	状态压缩里计数、汉明重量
clz(x)	统计最前面连续的 0 的个数（32 位）	计算最高位位置、floor(log2(x))、分桶
ctz(x)	统计末尾连续的 0 的个数	求最低位下标、子集枚举

这几个技巧看着不起眼，处理二进制状态、快速跳转、计数时却能省掉不少循环和查表。反正我是离不开它们了，先记下来，免得下次又得从头想。