具有相同数量的置位（1位）的下一个更大数字

 * @简介 [具有相同数量的置位（1位）的下一个更大数字]* 实现** @详细说明* 给定一个数字 x，找到在其二进制表示中具有相同数量的 1 位的下一个更大数字。例如，考虑 x = 12，它的二进制表示是 1100（在 32 位机器上不包括前导零）。它包含两个逻辑 1 位。具有两个逻辑 1 位的下一个更大数字是 17（二进制为 10001₂）。** 一个二进制数由两个数字组成。它们是 0 和 1。在计算机术语中，数字 1 被称为置位。

这个算法的逻辑基于二进制数的进位和位模式重组，确保找到比原数大且1的个数相同的最小数。以下是逐步解释：

核心逻辑

1. 定位最右侧的1：
   使用 x & -x 找到最右侧的1（如 1100 → 0100），目的是确定需要进位的位置。

2. 进位操作：
   将最右侧的1进位到高位（如 1100 + 0100 = 10000），生成更高位的1，形成数的基础框架。

3. 计算差异位模式：
   通过异或运算 x ^ nextHigherOneBit 得到所有变化的位（如 1100 ^ 10000 = 11100），标记出进位影响的所有位。

4. 调整位模式：

   • 除法：将差异位右移 log2(rightOne) 位（如 11100 / 0100 = 111），将右侧连续的1对齐到低位。

   • 再右移：消除多余的1（如 111 → 001），确保右侧的1数量与原数相同。

5. 合并结果：
   将进位后的高位与调整后的低位模式合并（如 10000 | 0001 = 10001），得到最终的最小符合条件的数。

数学原理

• 进位必要性：最小的增量必须通过将某个1左移，同时重组右侧的1到最低位。

• 模式调整：差异位中的1表示原数右侧被清空的位，调整后补回这些1的数量，确保总数不变。

示例解析（x=12, 二进制1100）

1. rightOne = 4（定位最右1）。

2. 进位得到16（10000）：提升一位。

3. 异或得28（11100）：显示进位影响的位。

4. 调整模式：28/4=7（111），右移两位得1（0001）。

5. 合并结果：16 | 1 = 17（10001），正确。

结论

该算法通过精确的位操作，高效地重组二进制位，确保在最小增幅下保持1的数量不变，时间复杂度为O(1)。

#include <cassert>   /// for assert
#include <iostream>  /// for IO operations/*** @namespace bit_manipulation* @brief Bit manipulation algorithms*/
namespace bit_manipulation {/*** @brief The main function implements checking the next number* @param x the number that will be calculated* @returns a number*/uint64_t next_higher_number(uint64_t x) {uint64_t rightOne = 0;uint64_t nextHigherOneBit = 0;uint64_t rightOnesPattern = 0;uint64_t next = 0;if (x) {// right most set bitrightOne = x & -static_cast<signed>(x);// reset the pattern and set next higher bit// left part of x will be herenextHigherOneBit = x + rightOne;// nextHigherOneBit is now part [D] of the above explanation.// isolate the patternrightOnesPattern = x ^ nextHigherOneBit;// right adjust patternrightOnesPattern = (rightOnesPattern) / rightOne;// correction factorrightOnesPattern >>= 2;// rightOnesPattern is now part [A] of the above explanation.// integrate new pattern (Add [D] and [A])next = nextHigherOneBit | rightOnesPattern;}return next;}}  // namespace bit_manipulation/*** @brief Self-test implementations* @returns void*/
static void test() {// x = 4 return 8assert(bit_manipulation::next_higher_number(4) == 8);// x = 6 return 9assert(bit_manipulation::next_higher_number(6) == 9);// x = 13 return 14assert(bit_manipulation::next_higher_number(13) == 14);// x = 64 return 128assert(bit_manipulation::next_higher_number(64) == 128);// x = 15 return 23assert(bit_manipulation::next_higher_number(15) == 23);// x= 32 return 64assert(bit_manipulation::next_higher_number(32) == 64);// x = 97 return 98assert(bit_manipulation::next_higher_number(97) == 98);// x = 1024 return 2048assert(bit_manipulation::next_higher_number(1024) == 2048);std::cout << "All test cases have successfully passed!" << std::endl;
}
/*** @brief Main function* @returns 0 on exit*/
int main() {test();  // run self-test implementationsreturn 0;
}

代码讲解：

核心思路

目标：将二进制中的01模式转换为10，并将右侧所有1移动到最低位。
例如：0011 1000 → 找到最右边的01 → 转换为10 → 变成0100 0011。

分步详解（以x=12为例）

x = 12（二进制 1100）

1. 找到最右边的1（rightOne）

nextHigherOneBit = x + rightOne;

• 计算过程：

  • x = 12 → 0000 1100

  • -x（补码）= 1111 0100

  • x & -x → 0000 0100（十进制4）

• 作用：定位最右侧的1，为后续进位做准备。

2. 生成进位后的数（nextHigherOneBit）

nextHigherOneBit = x + rightOne;

• 计算过程：

  • 12 + 4 = 16 → 0001 0000

• 原理：将最右侧的1进位（例如1100 → 10000），此时左侧的高位部分已确定。

3. 计算变化位模式（rightOnesPattern）

rightOnesPattern = x ^ nextHigherOneBit;

• 计算过程：

  • 12 ^ 16 = 0001 1100（十进制28）

• 解释：异或运算标记出所有发生变化的位（原数和新数的差异）。

4. 调整模式位置

rightOnesPattern = (rightOnesPattern) / rightOne; // 28/4=7 → 0111
rightOnesPattern >>= 2;                           // 0111 → 0001

• 步骤分解：

  1. 除以rightOne：将差异位右移到最低位。
     0001 1100 / 4 = 0000 0111（相当于右移2位）。

  2. 再右移2位：消除多余的1，保留需要移动到右侧的1。
     0000 0111 → 0000 0001。

• 目的：得到右侧需要补充的1的模式（即原数右侧连续的1减1）

5. 合并最终结果

next = nextHigherOneBit | rightOnesPattern;

• 计算过程：

  • 16 (10000) | 1 (00001) = 17 (10001)

• 效果：将进位后的高位与调整后的低位模式合并，形成最终结果。

关键位操作原理

1. x & -x：

   • 补码性质：-x = ~x + 1。

   • 结果保留最右边的1，其余位清零（如0100100 → 0000100）。

2. 异或运算：

   • 标记出所有因进位发生变化的位（例如进位后左侧新增的1和右侧清零的位）。

3. 模式调整：

   • 除法与右移：等效于将右侧的1重新排列到最低位，确保总位数不变。

---

时间复杂度

• O(1)：所有操作均为常数时间的位运算，不依赖数据规模。

---

测试用例全解析

输入x	二进制	输出	新二进制	验证步骤
6	0110	9	1001	rightOne=2 → 6+2=8 → 异或得14 → 14/2=7 → 7>>2=1 → 8|1=9
13	1101	14	1110	rightOne=1 → 13+1=14 → 异或=1 → 1>>2=0 → 14|0=14
97	01100001	98	01100010	rightOne=1 → 97+1=98 → 异或=3 → 3>>2=0 → 98|0=98

---

通过这种逐位操作，算法高效地重组二进制位，保证在最小增幅下维持1的数量不变。