位运算 - YHT's Note Repo

# 纲要 > 主干纲要、Hint/线索/路标 - **二进制逻辑运算**：针对单个二进制变量值的逻辑运算 - **移位操作**：左移 `<<` 与右移 `>>`； - **位模式处理**： - 针对二进制位模式 "**整体**" 的位操作； - 针对二进制位模式中 "**特定二进制位（最低位的 0 或 1）**" 的位操作； ⭐ - **位掩码**：常用位掩码的生成方式 - 用于**单个位**操作的位掩码及用途： - 提取、置 0、置 1、取反**某一指定位**； - 用于**范围**操作（**多个相邻位**）的位掩码 - 提取、置 0、置 1、取反**某一段位区间** - **位运算的应用**：常用的位运算技巧 ⭐ - **位运算与集合**：利用位运算来遍历、枚举集合 ⭐ - **位运算与组合搜索** %% # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** %% # 总览 ![image-20231104095047434](_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-2D63BC6E42542E9F3F392855D27520A0.png) %% `row[i]/2 == row[i+1]/2` 等价于 `row[i]^1 == row[i+1]` 来判断？与"1"**按位异或**即是**按位取反**，等价于将 `row[i]` 的最低位取反，判断取反后的结果是否与 `row[i+1]` 相同。若 row[i]最低位为 0，则其情侣的最低位应当为 1；反之若 row[i]最低位为 1，则其伴侣的最低位应当为0。 `~0` 将得到一个全 1 的 mask，无论机器的字大小是多少。在 32 位机器上也可以用 `0xFFFFFFFF` 表示，但后者是不可移植的。 %% > [!NOTE] C++中，若位运算符的操作数为 "**小整型**"，则会被自动提升为 `int` 或 `unsigned int` 类型。 > > 参见[^2]（P136），**小整型**包括 bool, char, signed char, unsigned char, short, unsigned short。 > > 例如 `unsigned char bits = 0b10010111;`，而 `~bits` 则将得到 `int` 类型的值 `-152`。 > **即 `bits` 首先执行零扩展，提升为了 `int` 类型，然后再取反**。 > # 二进制逻辑运算 ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-58200B3A9C41AD86068C88FBD3A04904.png|475]] 针对**单个二进制值** $b=\{0,1\}$ 的逻辑运算： - **按位与** - $(b\;\&\;1)==b$，不变 - $(b\;\&\;0) == 0$，**==置 0==** - **按位或** - ($b\;|\;1) == 1$，**==置 1==** - ($b\;|\;0) == b$，不变 - **按位异或** - $(b\;\oplus\;1)$，**==取反==** - $(b\;\oplus\;0) == b$ ，不变 - $(b\;\oplus\;b) == 0$ ，置 0 # 移位操作位移运算，表示对操作数的二进制表示**按位移动**。 ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-964D32C7F9131DADDCBDBB54A1E3C72B.png|475]] - **左移运算符 `X<<i`**：将第一个操作数 `X` 的**二进制表示向左移动指定的位数 `i`**， - 左移时，**从右边补充的是 0**，而**左边超出变量存储范围的位会被丢弃**。 - **右移运算符 `X>>i`**：将 `X` 的**二进制表示向右移动指定的位数 ` i `** - 对于 **==无符号==类型**， - **==逻辑右移==**： **从左边补充 0**； - 对于 **==有符号==类型**，具体行为**依赖于编译器**，可能是 - **==算术右移==**，即**从左边补充符号位**（符号位是 1（负数）则补 1，是 0（非负）则补 0）； - **==逻辑右移==**，即不论符号位，**统一从左边补 0**。 > [!info] 实际上，几乎所有 C/C++编译器的实现都对 "==有符号数==" 使用 "**==算术右移==**" > Java 则是明确规定 `>>` 为算术右移，`>>>` 为逻辑右移 > [!caution] 对有符号数应用 "左移"，可能改变有符号数的符号值。 > [!caution] 移位的位数不应超过或等于数据类型的位宽，否则行为未定义。 > > 例如，对于 `int` 类型（通常为 32 位），**移位的位数只能在 `[0, 31]`范围**。 - 在左移中， - $2^i==(1<<i)$ - `X<<i` 等价于**乘以 $2^i$**，结果为 $X*2^i$； - 在算术右移中： - `X>>i` 等价于**除以** $2^i$ **并向下取整（==向负无穷取整==）**，结果为 $\left\lfloor\frac{X}{\Large 2^i}\right\rfloor$。 - `(X + (1<<i)-1) >> i` 等价于**除以** $2^i$ **并向上取整（==向正无穷取整==）**，结果为 $\left\lceil\frac{X}{\Large 2^i}\right\rceil$。 - 本质上就是上取整 `(X+(2^i-1))/2^i` 的位运算实现上述**对于无符号数和有符号数（包括正负数）都成立** # 位模式处理 > 给定**二进制位模式**，对 "**二进制==位模式整体==**" 或者 "**其中某一==单个二进制位==**" 进行操作。 ## 对二进制位模式整体的处理给定位宽为 $w$ 的二进制位模式 $\large \vec{x}=[x_{w-1},\; x_{w-2},\; \cdots,\; x_{1},\; x_0]$ - **按位异或** - $\large (\vec{x} \;^{\wedge}\; \vec{x})==0$，**==归零==** （可用于**判断==相等==**） - $\large (\vec{x} \;^{\wedge}\; 0)==\vec{x}$，**==恒等==** ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-E5AAC047AB237986CCA411B945226AEF.png|309]] ## 对二进制位模式中特定二进制位的处理——位操作 ⭐ > 特定二进制位：针对最低位的 0 或 1 ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-F0F29E56565DDA07FD5BDEDB223D5926.png|680]] 基本操作： - `x - 1` ：将**最低位的 1 以及右侧的 0 全反转**； - `x + 1` ：将**最低位的 0 以及右侧的 1 全反转**； - `-x` ：**保留最低位的 1 及右侧 0 不变**，而**反转其余高位**。 --- ###### 将 $\large \vec{x}$ 中的==**最低位 1 置为 0==** - 操作：`res = x & (x-1); - 说明：`x-1` 会让最低位的 1 变成 0，同时其后的 0 全部反转为 1； ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-29CD4DFDDC8F3E63A813FFD003D5782A.png|300]] ###### 将 $\large \vec{x}$ 中 **==最低位 0 置位为 1==**： - 操作：`res = x | (x+1)` ![[Excalidraw-Solution/位运算_1.excalidraw.svg|375]] %%[[Excalidraw-Solution/位运算_1.excalidraw.md|🖋 Edit in Excalidraw]]%% --- ###### **==提取==** $\large \vec{x}$ 中的**最低位 $0$**：提取最后一位 0（置为 1），其余位置全为 0 - 操作：`res = ~x & (x+1)` ![[Excalidraw-Solution/位运算_2.excalidraw.svg|375]] %%[[Excalidraw-Solution/位运算_2.excalidraw.md|🖋 Edit in Excalidraw]]%% ###### **==提取==** $\large \vec{x}$ 中的**最低位的 $1$**：保留二进制位最后一位 1，其余置 0 - 操作： - 方式一： `res = x & (-x);` 取相反数得到的补码，**最低位 1 及其右侧的 0 不变** - 方式二： `res = x ^ (x&(x-1))`，即消除最低位的 1 后进行异或； ![[Excalidraw-Solution/位运算_3.excalidraw.svg|325]] %%[[Excalidraw-Solution/位运算_3.excalidraw.md|🖋 Edit in Excalidraw]]%% --- ###### 将 $\large \vec{x}$ 中==**最低位 1 右侧的 0 全置 1**== - 操作：`res = x | (x-1)` ![[Excalidraw-Solution/位运算_4.excalidraw.svg|375]] %%[[Excalidraw-Solution/位运算_4.excalidraw.md|🖋 Edit in Excalidraw]]%% ###### 将 $\large \vec{x}$ 中==**最低位 0 右侧的 1 全清 0**==： - 操作：`res = X & (X+1)` ![[Excalidraw-Solution/位运算_5.excalidraw.svg|390]] %%[[Excalidraw-Solution/位运算_5.excalidraw.md|🖋 Edit in Excalidraw]]%% --- # 位掩码 Bitmask ![[_attachment/00-数据结构与算法笔记/专题总结/位运算.assets/IMG-位运算-524211AD222ECDF2BE60C51C1B89A7B5.png|609]] 给定一个**位宽为 $w$** 的二进制位模式 $\large X=\vec{x}=[x_{w-1},\; x_{w-2},\; \cdots,\; x_{1},\; x_0]$，对于指定二进制位 $x_i=\{0,1\}$。 ### 用于单个位操作的掩码 - 仅 $\large b_i$ 位为 $1$ ，其余位全 0 的掩码：$\text{mask}:\; 00\ldots0\overset{i}{1}0\dots0\overset{0}0$ - $\text{mask}==(1<<i)$ - 用途： - **==置 1== 特定位**——对 $\large x_i$ 置 1 ：`x |= (1<<i)` - **==取反== 特定位**——对 $\large x_i$ 取反：`x ^= (1<<i)` - **==提取== 特定位**——取 $\large x_i$ 位值：`res = x & (1<<i)`； - 仅 $\large b_i$ 位为 0，其余位全 1 的掩码：$\text{mask}:\; 11\ldots1\overset{i}{0}1\dots1\overset{0}1$ - $\text{mask}==\sim(1<<i)$ - 用途： - **==置 0== 特定位**——对 $\large x_i$ 置 0：`x &= ~(1<<i);` ### 用于位范围操作的掩码 - 高位全 0，低 $i$ 位全为 1 的掩码：$\text{mask}:\; 00\ldots00\overbrace{11 \ldots 11}^{低 i 位}$ - `mask = (1<<i) - 1` - 用途： - **==提取==低位**——**保留 $\large \vec{x}$ 低 $i$ 位，清除高位**：`res = x & ((1<<i) - 1)` - **低位==置 1==**——**将 $\large \vec{x}$ 的低 $i$ 位全==置 1==**：`x |= ((1<<i) - 1)` - **高位==置 0==**——**将 $\large \vec{x}$ 的高位全==置 0==**：`x &= ((1<<i) - 1)` - 高位全 1，低 $i$ 位全为 0 的掩码：$\text{mask}:\; 11\ldots11\overbrace{00 \ldots 00}^{低 i 位}$ - `mask = ~((1 << i)-1)` - 用途： - **低位置 0**——**对 $\large \vec{x}$ 的低 $i$ 位全==置 0==**：`x &= ~((1<<i) - 1);` - **高位置 1**——**将 $\large \vec{x}$ 的高位全==置 1==**：`x |= ~((1<<i) - 1);` - **==提取==高位**——**保留 $\large \vec{x}$ 高位，清除低 i 位位**：`res = x & ~((1<<i) - 1)` ## 特别掩码 - 为 **负数** `x` 得到**全 1 掩码**，为**非负数** `x` 得到**全 0 掩码**：`mask = x >> 31`； - 为 **0 值** `x` 得到**全 0 掩码**，为**非 0 值** `x` 得到**全 1 掩码**： - 方式一：`mask = (x | -x) >> 31 = (x | (~x+1)) >> 31`； ❇️ - 方式二：`mask = ~!!(x) + 1`； ## 掩码应用 #### 通过掩码遍历二进制位 ```cpp // 从高位遍历到低位 template <typename T> void traverse_bits(T num) { size_t bits = sizeof(num) * 8; while (bits--) { int mask = 1<<bits; // 每次构造mask if (num & mask) { cout << "1"; } else { cout << "0"; } } cout << endl; } // 从低位到高位遍历 template <typename T> void traverse_bits(T num) { size_t bits = sizeof(num) * 8; int mask = 1; for (int i = 0; i < bits - 1; ++i) { if (num & mask) { cout << "1"; } else { cout << "0"; } mask <<= 1; // 左移mask } cout << endl; } ``` # 位运算的应用 > 下方示例以由**补码**表示的 "**32 位有符号整数**" 变量为例，变量位宽相同。 ### 判断 - 判断 `x` 是否**为 0**：`!x` - 判断 `x` 是否**为负**：`(x >> 31) & 1` 或者 `!!(x >> 31)`，为负返回 1，为正返回 0； - 判断 `x` 的**第 `i` 位及以上是否存在 "1"** ：`!!(x >> i)`，存在返回 1，不存在返回 0； - 思路：右移将低 `i` 位去掉后，再检查是否非 0; - 判断两个数是否**异号**：`res = ((x ^ y) >> 31) & 1`，异号返回 1，同号返回 0； - 或者 `(x^y) < 0` - 判断两个数是否**相等**： `equal = !(x ^ y)`，相等返回 1，不同返回 0； - 判断两个有符号整数是否 `x <= y`： ```cpp int isLessOrEqual(int x, int y) { // x <= y, considering the sign of x and y: // 1) different sign and y is positive // 2) same sign and y - x is positive or 0 int sign_x = (x >> 31) & 1; int sign_y = (y >> 31) & 1; int flag1 = sign_x & !sign_y; // x is negative and y is positive int flag2 = !(sign_x ^ sign_y) & !((y + (~x + 1)) >> 31); // x and y have same sign and y - x is positive or 0 return flag1 | flag2; } ``` - 判断一个数是否为 `2` 的整数次方：二进制位中**只有 1 个 1**； - 判断一个数是否能够**被 `2` 的整数次幂 `m` 整除**： - `!(x & (m-1))`，返回 1 表示能够整除，返回 0 表示不能整除； - 判断 `x` 的二进制低`n`位中不包含 "**==连续两个相邻== 0**"： - `x ^= (1<<n) - 1; bool res = (x & (x>>1)) != 0; ` - 判断**奇偶性**：`isOdd = x & 1`； - 判断两个数**奇偶性**是否**不同**：`diff = (x ^ y) & 1`，不同返回 1，相同返回 0； - 注意 `&` 的优先级高于 `^` - 示例：[[99-题解/leetcode/lc-3151 特殊数组 I|lc-3151 特殊数组 I]] - 判断**位模式位于某个范围**： - 以判断低 4 位是否为 `[0000, 1001]` 为例： - 获取低 4 位：`int low_4_bit = x & 0xf;` - 判断**方式一**：**第 3 位为 0**，或者**第 3 位为 1 且第 1、2 位为 0** - 第 3 位为 0，则 `low_4_bit` 右移 3 位后为全 0； - 第 3 位为 1 且第 1、2 位为 0，则 `low_4_bit` 与 `0b0110` **按位与为 0**； - `!(low_4_bit >> 3) & !(low_4_bit & 0x6)` - 判断**方式二**：**拆分成两个区间：`[0000, 0111]` 与 `[1000, 1001]`；** - `[0000, 0111]` 只有**后三位变动**，因此与 **==掩码 `1000`==** 按位与的结果必然是 `0000`； - `[1000, 1001]` 只有**最低位变动**，因此与 **==掩码 `1110`==** 按位与的结果必然是 `1000`； - `!(low_4_bit&0x8) | !(low_4_bit&0xe ^ 0x8)` --- ### 求值 - 将**任意非 0 整数值转换为 1**：`!!x`，若 **`x` 非 0** 则返回 1； - 求**相反数**（即补码的加法逆元）：`-x == ~x+1`，**取反+1**； - 求**减一的值**： `x-1 = ~(~x+1)`，**取反+1 后再取反** - 求**整数`x`的绝对值**：`abs(x)` - 方式一：`abs(x) == (x >= 0) ? x : (~x+1)` - 方式二：`mask = x >>31; abs(x) = (x + mask) ^ mask`； ❇️ - 对于负数，`mask` 全 1 表示 `-1`， `x + mask == x - 1`，相当于先取反最低位 1 及其右侧的 0， 然后 `^ mask` 整个取反，最终结果**相较于`x` 取反了高位，而保留了最低位 1 及其右侧的 0 不变**； - 对于正数，`mask`全 0，不改变； - 🚨不能正确处理给定位宽下的最大负值，因为没有对应的绝对值正值的表示 - 将 `x` 的 **==低 `n` 位==取反**：`x ^ ((1<<n) - 1)` - **字母大小写取反**：`oppo = ch ^ 32` - 说明：小写字母比大写字母的 **ASCII 码值大 32**，即 `(1<<5)`，例如 A 是 65，a 是 97。故二者 ASCII 码的**二进制表示==只有右起第 6 位不同==**，该位取反即可。 - 求**模 $2^n$** `x % 2^n`：`res = x & ((1<<n) - 1)` - 交换 `short` （16 位）的两个字节： - `res = (x << 8) | ((x >> 8) & 0xFF)` - **规定两个"对立"的值 `x` 和 `y`**，**给定 `var` 为其中一值**，求其相反值：`opposite = var ^ x ^ y` - [[99-题解/leetcode/lc-1958 检查操作是否合法|lc-1958 检查操作是否合法]] - [[99-题解/leetcode/lc-832 翻转图像|lc-832 翻转图像]] --- ### 浮点数相关运算 - 浮点数**取绝对值**（`fabs`） - 浮点数**取相反数** - 浮点数**置 0（得到`0.0`）** --- ### 奇偶配对 - 取「**偶-奇**」两两一组的 **==配对==** 数字：`res = x ^ 1` - **`x` 为奇数**时，`x^1 == x-1`，取得与 `x` 配对的**前一个偶数**； - **`x` 为偶数**时，`x^1 == x+1`，取得与 `x` 配对的**后一个奇数**； - 示例：[[99-题解/leetcode/lc-540 有序数组中的单一元素|lc-540 有序数组中的单一元素]] --- ## 逐位遍历各个二进制位两种方式： - 方式一：**用 ==`mask`== 遍历各个位，==逐位取数==**（推荐**从 `mask = 1` 起，从低位到高位**遍历） - 方式二：**将 `x` ==逐位右移==直至为 0**（只能用于 **==非负数==**，否则**负数算术右移**始终为负） #### 方式一：通过 mask 进行逐位遍历 ##### 从低位到高位遍历（对正负数皆可） `i` 从 0 起，左移至多 31 位或 63 位 ```cpp // 对于int for (int i = 0; i < 31; ++i) { int mask = 1 << i; if (mask & x) ++cnt1; } // 对于long long for (long long i = 0; i < 63; ++i) { int mask = 1LL << i; // 1LL if (mask & x) ++cnt1; } ``` ##### 从高位到低位遍历（只能用于正数） i 只能从高 `30` 位和高`62` 位起始！`mask` 必须 **==避开符号位==**，否则 **==算术右移后会破坏掩码==**。 ```cpp // 对于int for (int i = 30; i >= 0; --i) { int mask = 1 <<i; if (mask & x) ++cnt1; } // 对于long long for (long long i = 62; i >= 0; --i) { int mask == 1LL << i; // 1LL if (mask & x) ++cnt1; } ``` #### 方式二：**将 `x` ==逐位右移==直至为 0**（只能用于正数） ```cpp while (x) { cnt1 += (x & 1); x >>= 1; // 每次取最低位, 而后右移消除最低位 } // 或者通过j控制x右移量, 保持x不变 int j = 0; while (x >> j) { cnt1 += (x >> j) & 1; ++j; } ``` 注意踩坑点： 1. **避免移位溢出**：**左移可能导致溢出**（未定义行为）: 1. 对 `int` 类型通过`mask`逐位遍历时，需要取 `mask = 1<<i`，$i=[0, 31]$; 2. 对 `long long` 类型通过 `mask` 逐位遍历时，需要取 `mask = 1LL << i`，$i=[0, 63]$； 2. 不要通过 "**==负数==右移**" 进行逐位遍历：**负数算术右移始终负数**！ --- ## 实现操作符 #### 位运算实现逻辑非 `!x` `!x` 在 `x == 0` 时返回 `1`，在 `x != 0` 时返回 `-1`，因此需要根据 **0** 与**非 0 值** 的差异来进行辨别。 - 当 `x == 0` 时，`x` 与 `-x` 的**符号位相同**； - 当 `x != 0` 时，`x` 与 `-x` 的**符号位不同** 因此可利用 `(x | -x) >> 31` 在 `x == 0` 时为 0，在 `x != 0` 时为 **全 1（`0xff...ff`）** 的特点，可以进行判断。 ```cpp int logicalNeg(int x) { // ((x | -x) >> 31) + 1 return ((x | (~x + 1)) >> 31) + 1; } ``` #### 位运算实现两数交换位运算实现**同位宽的两数交换** `swap(a, b)`（无需借助临时变量） ```cpp template <typename T> int inplace_swap(T& a, T& b) { if (&a == &b) return; // 不能对同一个数自身应用下列位操作, 否则得到全0 a ^= b; // 记两个数原始值为a0和b0, a0^b0得到的位模式d中, 1表示二者不同的位, 此时将该位模式d赋给变量a b ^= a; // 由于此时变量a的位模式d中1表示的是a0与b0不同的位, 因此b0^a即是将b0中与a0不同的位全部取反, 由此得到变量b的值为a0. a ^= b; // 此时a存储着位模式d, 而b存储着值a0的位模式, 因此a^b即d^a0, 得到变量a的值变为b0, 完成交换. } ``` #### 位运算实现算术加法 `a + b` 通过**按位与**和**按位异或**来实现算术加法。其中，**异或**相当于二进制下的**无进位加法**。 - **无进位的相加结果**：$\large \vec{x} \;^{\wedge}\;\vec{y}$ - **相加所得进位**：$\large((\vec{x} \& \vec{y})<<1)$ ```cpp template <typename T> T add(T a, T b) { while (b) { T carry = (a&b)<<1; // 获取无进位的相加结果 a = a^b; // 获取相加所得的进位 b = carry; // 若存在进位则持续运算 } return a; } ``` - $\large (\vec{x} + \sim\vec{x}) == \sim 0$，取反相加，得到**全 1 的位模式** #### 位运算实现算术乘法通过**位移**、**二进制加法或减法**实现**乘法**。 #### 位运算实现与 2 的幂次的除法（截断整除）通过位运算实现 `a / 2^k` （**截断除法，向 0 取整**）： - 对于**正数**：直接右移 k 位，向下取整，即为**向 0 截断**； - 对于**负数**：先**加上偏移量** $2^k-1$，再**右移 k 位**，通过 "**向上取整**" 来得到 "**向 0 取整**"。 - $\large \left\lceil\frac{a}{2^k}\right\rceil=\left\lfloor\frac{a+2^k-1}{2^k}\right\rfloor$ > [!NOTE] 直接右移 k 位是 "**==向下取整==**"，因此对于负数需要调整为 "**==向上取整==**"，从而实现有符号数的 "**==截断除法==**" ```cpp #include <iostream> #include <cmath> using namespace std; // 实现对2的k次幂的 "截断整除" int truncateDivide(int x, int k) { // 若x为正数, 直接右移k位向下取整 // 若x为负数, 需要向上取整: (x + 2^k - 1) / 2^k int bias = ~(~((x >> 31 & 1) << k) + 1); return (x + bias) >> k; } int main(int argc, char** argv) { cout << truncateDivide(10, 2) << endl; cout << 10 / (int) pow(2, 2) << endl; return 0; } ``` # 位运算与集合位运算具有「**并行计算**」的特点，因此可以**用位模式来表示一个集合** [^1]，借助位运算来高效实现集合相关运算，例如：求**交集**、**并集**。用二进制位模式表示集合：从低到高**第 $i$ 位为 $1$ 表示元素在集合中**，为 $0$ 则表示不在。 #### 遍历集合给定表示集合的二进制位模式, **遍历集合中的项** ```cpp // 给定表示集合的二进制位模式, 遍历集合中的项 for (int i = 0; i < n; i++) { if ((s >> i) & 1) { // i 在 s 中 // 处理 i 的逻辑 } } ``` #### 枚举集合给定位宽 `n`，用二进制位模式表示集合，**枚举从空集 ∅ 到全集 U 的所有情况**。 ```cpp for (int s = 0; s < (1 << n); s++) { // 处理 s 的逻辑 } ``` 设集合为 $s$，**从大到小**枚举 **$s$ 的所有非空子集 $sub$**： ```cpp for (int sub = s; sub; sub = (sub - 1) & s) { // 处理 sub 的逻辑 } ``` # 位运算与组合搜索 ### 从大到小枚举给定集合的所有非空子集给定一个**二进制位模式表示的集合 $s$**，**==从大到小==** 枚举 **$s$ 的所有==非空子集 $sub$==**。 $s$ 二进制位中的 "1" 表示集合里具有该元素，其子集 $sub$ 即是**这些位上的 "1" 的子集所对应的二进制位模式**。算法过程： 1. 初始时令 `sub = s`； 2. 此后每一步，令 `sub = (sub - 1) & s`； - `sub - 1` 会使得 `sub` 中最低位 1 及右侧的 0 全反转； - `(sub - 1) & s` 会使得**每次消除当前最低位的1**，**同时==将原 `s` 中该位右侧的 1 全补上**==，从而实现**枚举"子集"**。如果对空集再做 `sub=(sub-1)&s` 操作，则将会回到 `sub = s`。算法过程示意图： ![[Excalidraw-Solution/位运算_6.excalidraw.svg|476]] %%[[Excalidraw-Solution/位运算_6.excalidraw.md|🖋 Edit in Excalidraw]]%% 实现 **==从大到小==** 枚举 **$s$ 的所有==非空子集== $sub$**： ```cpp for (int sub = s; sub; sub = (sub - 1) & s) { // 处理 sub 的逻辑 } ``` 实现 **==从大到小==** 枚举 **$s$ 的所有==子集== $sub$**（包括空集）： ```cpp int sub = s; do { // 处理 sub 的逻辑 sub = (sub - 1) & s; } while (sub != s); ``` ### 求下一个具有指定数量的二进制 "1" 位的更大值 **Gosper's Hack 方法**，也称为“HAKMEM 175”。给定**具有 k 个置位的二进制数** p，其能**以 $O(1)$ 时间算出==下一个大于 `p` 且同样具有 `k` 个置位==的数**。^y6utxb ##### 算法思想 > [!caution] 要得到 "**"==置位数量相同==" 的 "下一个==更大值==**"，不能直接在**低位添加 1**，也不能直接把 **"高位的 1" 挪到低位**。正确做法： **在最低位 1 上产生进位，使得==从最低位 1 起始==的==多个连续 1== 因进位变为 0，再在低位==补上==相等数量的 1**。 **Gosper's Hack 算法的思想**如下： ![[Excalidraw-Solution/位运算.excalidraw.svg|754]] %% [[Excalidraw-Solution/位运算.excalidraw.md|🖋 Edit in Excalidraw]] %% > [!NOTE] 差异位体现的是 “进位前” 和 “进位后” 不同的位。 ##### 算法步骤 1. **获取 `p` 最低位的 1**：`lb = p & (-p);` 2. **添加**：**在 `p` 的最低位 1 上产生进位**，得到**进位后的位模式**：`x = p + lb;` 3. **重排**：得到 `p` 与 `x` 的**差异位**并 **==将差异位移动到低位部分，再右移去除两位==** ：`(p ^ x / lb >> 2)` 4. **合并**：将上一步结果与 `x` 做按位与，**==在低位部分补上"1"==**： ` p' = (p ^ x / lb >> 2) | x ` 所得的 `p'` 即为目标结果——**具有与 `p` 相同数量的二进制位 1** 且**大于 `p`** 的**下一个较大值**。 > [!example] 算法步骤的示意图 > > ![[Excalidraw-Solution/位运算_7.excalidraw.svg|400]] > %%[[Excalidraw-Solution/位运算_7.excalidraw.md|🖋 Edit in Excalidraw]]%% > > #### 实现 ```cpp int GetNextNumWithSameNumberOfSettingBits(int p) { int lb = p & (-p); int x = p + lb; int next = (p ^ x / lb >> 2) | x; return next; } ``` 枚举恰好具有 k 位 1 的所有位模式： ```cpp // 枚举具有k位1的所有位模式 int n = 12; // 给定位宽n int p = (1<<k) - 1; while (s < (1<<n)) { // ... int lb = p & (-p); int x = p + lb; p = ((p ^ x) / lb) } ``` # 编译器 gcc/clang 内置的位运算函数 > 参考：[GCC自带的一些builtin内建函数](https://tomsworkspace.github.io/2021/02/27/GCC%E8%87%AA%E5%B8%A6%E7%9A%84%E4%B8%80%E4%BA%9Bbuiltin%E5%86%85%E5%BB%BA%E5%87%BD%E6%95%B0/) GCC 和 clang **编译器中自带的内建函数**。这些 `_builtin_*` 形式的内建函数一般是基于不同硬件平台采用专门的硬件指令实现的，因此性能较高。 - `__builtin_popcount()`：返回 x 的二进制表示中 **`1` 的个数**。 - `__builtin_clz()`：返回 x 二进制表示中**前导 0 的数量**。 - `__builtin_ctz()`：返回 x 二进制表示中**后缀 0 的数量**。 ##### `int __builtin_ffs(unsigned int x)` 返回 x 二进制表示中**从最低位开始首个 `1` 位的位置**（位置计数以最低位为 1 开始） ```c++ int lowestBitPosition(unsigned int num) { return __builtin_ffs(num) - 1; // 将位置下标改为从0开始 } ``` ##### `int __builtin_clz(unsigned int x)` 返回 x 二进制表示中**前导 0 的数量**（count leading zeros，**clz**）该函数**未定义==输入参数为"0"==的情况**，因此**必须自行检查**，否则导致未定义行为。 ```c++ // 通过__builtin_cls()来得到最高位"1"的位置下标 int highestBitPosition(unsigned int num) { if (num == 0) return -1; // 没有1 return 32 - __builtin_clz(num) - 1; // 位置下标从0起 } ``` ##### `int __builtin_ctz(unsigned int x)` 返回 x 的二进制表示中**从最低位起的连续的 0 的个数**。（count trailing zeros，**ctz**）该函数未定义输入参数为"0"的情况，因此必须自行检查，否则导致未定义行为。 ##### `int __builtin_popcount(unsigned int x)` : 返回 x 的二进制表示中 **`1` 的个数**。 ##### `int __builtin_parity(unsigned int x)` : 返回 x 的**奇偶校验位**，即 x 的 **`1` 的个数模 2**的结果。 # 参考资料 - [【算法】位运算技巧 - Nemo& - 博客园](https://www.cnblogs.com/blknemo/p/14470610.html) - [从集合论到位运算，常见位运算技巧分类总结！](https://leetcode.cn/circle/discuss/CaOJ45/) - [【题单】位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）](https://leetcode.cn/circle/discuss/dHn9Vk/) - [位运算有什么奇技淫巧？](https://www.zhihu.com/question/38206659/answer/76484782) - [位运算的奇技淫巧：Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) # Footnotes [^1]: [分享｜从集合论到位运算，常见位运算技巧分类总结！ - 力扣（LeetCode）](https://leetcode.cn/circle/discuss/CaOJ45/) [^2]: 《C++ Primer》