在位运算和数论中，快速寻找**不大于 $x$ 的最大 2 的幂次方**（数学上表示为 $2^{\lfloor \log_2 x \rfloor}$）是一个经典且非常实用的问题。在底层算法（如哈希表扩容、树状数组、二分搜索优化）中经常会用到。

下面为您介绍几种在 C++ 中快速实现该功能的方法，从现代 C++ 标准库到高效的纯位运算。

---

### 方法 1：C++20 标准库 `std::bit_floor`（最现代、安全）
如果您可以使用 C++20，标准库 `<bit>` 头文件中已经直接提供了该功能函数 `std::bit_floor`：

```cpp
#include <bit>
#include <iostream>

int main() {
    unsigned int x = 5;
    // 返回不大于 x 的最大 2 的幂次方
    std::cout << std::bit_floor(x) << std::endl; // 输出 4
    return 0;
}
```
* **优点**：由编译器高度优化，安全且可读性极佳。

---

### 方法 2：利用编译器内置指令（C++11 常用，最快 $O(1)$）
在 C++11/14/17 中，我们可以使用 GCC/Clang 提供的编译器内置指令（Intrinsics）来直接获取 CPU 级别的硬件加速。

其核心思想是：**计算 $x$ 的二进制表示中前导零（Leading Zeros）的个数**。
例如，32 位整数中，若最高位的 `1` 在第 $k$ 位（从右往左数，0-indexed），那么前导零的个数就是 $31 - k$。因此，最高位的 `1` 代表的值就是 $1 \ll k$。

```cpp
#include <iostream>

uint32_t highestPowerOfTwo(uint32_t x) {
    if (x == 0) return 0;
    // __builtin_clz(x) 返回 x 的前导零个数
    int leading_zeros = __builtin_clz(x); 
    return 1U << (31 - leading_zeros);
}

int main() {
    std::cout << highestPowerOfTwo(5) << std::endl;  // 输出 4 (2^2)
    std::cout << highestPowerOfTwo(8) << std::endl;  // 输出 8 (2^3)
    std::cout << highestPowerOfTwo(15) << std::endl; // 输出 8 (2^3)
    return 0;
}
```
* **优点**：通常会直接编译成单条汇编指令（如 x86 上的 `BSR` 或 `LZCNT`），速度是所有方法中最快的。
* **注意**：传入 `0` 会导致未定义行为，因此需要先特判 `x == 0`。对于 64 位无符号整数，应使用 `__builtin_clzll`。

---

### 方法 3：经典的二进制位扩散算法（跨平台、硬件无关 $O(1)$）
如果您需要编写不依赖任何编译器特性（如 MSVC、GCC 均通用）的跨平台代码，可以使用经典的书籍《黑客秘笈》（Hacker's Delight）中的**位扩散（Bit Smearing）算法**。

此时的 $x$ 在二进制下会变成类似于 `00...01111` 的形式。
接着，我们只需通过 `x - (x >> 1)` 或者 `x ^ (x >> 1)`，就能将低位的 `1` 全部抹去，仅保留最高位的 `1`。

#### C++ 代码实现：
```cpp
#include <iostream>

uint32_t highestPowerOfTwoBitwise(uint32_t x) {
    if (x == 0) return 0;
    
    // 扩散最高位的 1 到所有低位
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    
    // 抹去低位的 1，只留最高位
    return x - (x >> 1); // 也可以用 x ^ (x >> 1)
}

int main() {
    std::cout << highestPowerOfTwoBitwise(5) << std::endl;  // 5 (0101) -> 7 (0111) -> 4 (0100)
    std::cout << highestPowerOfTwoBitwise(1) << std::endl;  // 1 (0001) -> 1 (0001) -> 1 (0001)
    return 0;
}
```
* **数学演示**（以 $x = 5$ 为例）：
  * $5$ 的二进制是 `0101`
  * 执行扩散后，变为 `0111`（即 7）
  * `x >> 1` 得到 `0011`（即 3）
  * `x - (x >> 1)` 计算为 $7 - 3 = 4$（即 `0100`），正好是不大于 5 的最大 2 的幂。

---

### 四、 相关拓展问题

在解决类似数论/位运算问题时，还有两个极为相似且频繁被问及的问题：

#### 1. 寻找 严格小于 $x$ 的最大 2 的幂
如果题目要求的是“**严格小于**”，那么当 $x = 8$ 时，我们应该返回 $4$。
* **解决思路**：只需对输入进行预处理，将问题转化为求“**不大于 $x-1$ 的最大 2 的幂**”。
* **实现**：在上述任何方法的开头，将 `x` 替换为 `x - 1` 即可（注意特判 `x <= 1` 的边界情况）。

#### 2. 寻找 能整除 $x$ 的最大 2 的幂（Lowbit）
在树状数组（Binary Indexed Tree）中，我们经常需要寻找**能整除 $x$ 的最大 2 的幂**（即 $x$ 的二进制表示中，最右侧、最低位的 `1` 所代表的值）。
* **解决思路**：利用计算机的补码特性，这可以直接通过一条极其简单的位运算实现：
  $$lowbit(x) = x \ \& \ (-x)$$
* **原理**：$-x$ 在补码表示下等于 `~x + 1`。在最右侧的 `1` 之前的所有位会全部取反，而最右侧的 `1` 及其右边的 `0` 保持不变，两者按位与后便只剩最右侧的 `1`。
* **示例**：
  * 若 $x = 12$（二进制 `1100`），则 $12\ \&\ (-12)$ 返回 $4$（二进制 `0100`）。因为 4 是能整除 12 的最大 2 的幂。

在位运算和数论中，快速寻找不大于 $x$ 的最大 2 的幂次方（数学上表示为 $2^{\lfloor \log_2 x \rfloor}$）是一个经典且非常实用的问题。在底层算法（如哈希表扩容、树状数组、二分搜索优化）中经常会用到。

下面为您介绍几种在 C++ 中快速实现该功能的方法，从现代 C++ 标准库到高效的纯位运算。

方法 1：C++20 标准库 `std::bit_floor`（最现代、安全）

如果您可以使用 C++20，标准库 <bit> 头文件中已经直接提供了该功能函数 std::bit_floor：

#include <bit>
#include <iostream>

int main() {
    unsigned int x = 5;
    // 返回不大于 x 的最大 2 的幂次方
    std::cout << std::bit_floor(x) << std::endl; // 输出 4
    return 0;
}

优点：由编译器高度优化，安全且可读性极佳。

方法 2：利用编译器内置指令（C++11 常用，最快 $O(1)$）

在 C++11/14/17 中，我们可以使用 GCC/Clang 提供的编译器内置指令（Intrinsics）来直接获取 CPU 级别的硬件加速。

其核心思想是：计算 $x$ 的二进制表示中前导零（Leading Zeros）的个数。例如，32 位整数中，若最高位的 1 在第 $k$ 位（从右往左数，0-indexed），那么前导零的个数就是 $31 - k$。因此，最高位的 1 代表的值就是 $1 \ll k$。

#include <iostream>

uint32_t highestPowerOfTwo(uint32_t x) {
    if (x == 0) return 0;
    // __builtin_clz(x) 返回 x 的前导零个数
    int leading_zeros = __builtin_clz(x); 
    return 1U << (31 - leading_zeros);
}

int main() {
    std::cout << highestPowerOfTwo(5) << std::endl;  // 输出 4 (2^2)
    std::cout << highestPowerOfTwo(8) << std::endl;  // 输出 8 (2^3)
    std::cout << highestPowerOfTwo(15) << std::endl; // 输出 8 (2^3)
    return 0;
}

优点：通常会直接编译成单条汇编指令（如 x86 上的 BSR 或 LZCNT），速度是所有方法中最快的。
注意：传入 0 会导致未定义行为，因此需要先特判 x == 0。对于 64 位无符号整数，应使用 __builtin_clzll。

方法 3：经典的二进制位扩散算法（跨平台、硬件无关 $O(1)$）

如果您需要编写不依赖任何编译器特性（如 MSVC、GCC 均通用）的跨平台代码，可以使用经典的书籍《黑客秘笈》（Hacker's Delight）中的位扩散（Bit Smearing）算法。

算法逻辑：

此时的 $x$ 在二进制下会变成类似于 00...01111 的形式。接着，我们只需通过 x - (x >> 1) 或者 x ^ (x >> 1)，就能将低位的 1 全部抹去，仅保留最高位的 1。

C++ 代码实现：

#include <iostream>

uint32_t highestPowerOfTwoBitwise(uint32_t x) {
    if (x == 0) return 0;

    // 扩散最高位的 1 到所有低位
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;

    // 抹去低位的 1，只留最高位
    return x - (x >> 1); // 也可以用 x ^ (x >> 1)
}

int main() {
    std::cout << highestPowerOfTwoBitwise(5) << std::endl;  // 5 (0101) -> 7 (0111) -> 4 (0100)
    std::cout << highestPowerOfTwoBitwise(1) << std::endl;  // 1 (0001) -> 1 (0001) -> 1 (0001)
    return 0;
}

数学演示（以 $x = 5$ 为例）：
$5$ 的二进制是 0101
执行扩散后，变为 0111（即 7）
x >> 1 得到 0011（即 3）
x - (x >> 1) 计算为 $7 - 3 = 4$（即 0100），正好是不大于 5 的最大 2 的幂。

四、相关拓展问题

在解决类似数论/位运算问题时，还有两个极为相似且频繁被问及的问题：

1. 寻找严格小于 $x$ 的最大 2 的幂

如果题目要求的是“严格小于”，那么当 $x = 8$ 时，我们应该返回 $4$。 * 解决思路：只需对输入进行预处理，将问题转化为求“不大于 $x-1$ 的最大 2 的幂”。 * 实现：在上述任何方法的开头，将 x 替换为 x - 1 即可（注意特判 x <= 1 的边界情况）。

2. 寻找能整除 $x$ 的最大 2 的幂（Lowbit）

在树状数组（Binary Indexed Tree）中，我们经常需要寻找能整除 $x$ 的最大 2 的幂（即 $x$ 的二进制表示中，最右侧、最低位的 1 所代表的值）。 * 解决思路：利用计算机的补码特性，这可以直接通过一条极其简单的位运算实现： $$lowbit(x) = x \ \& \ (-x)$$ * 原理：$-x$ 在补码表示下等于 ~x + 1。在最右侧的 1 之前的所有位会全部取反，而最右侧的 1 及其右边的 0 保持不变，两者按位与后便只剩最右侧的 1。 * 示例： * 若 $x = 12$（二进制 1100），则 $12\ \&\ (-12)$ 返回 $4$（二进制 0100）。因为 4 是能整除 12 的最大 2 的幂。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

不大于 $x$ 的最大 2 的幂次方

方法 1：C++20 标准库 std::bit_floor（最现代、安全）