如何用C++高效判断一个正整数是否为二进制幸运数字？

Question

**常见技术问题：** “二进制幸运数字”通常定义为：其二进制表示中，0 的个数恰好等于 1 的个数，且最高位必须为 1（即无前导零的规范表示）。例如，6（110₂）含两个 1、一个 0 → 不满足；9（1001₂）含两个 1、两个 0 → 是二进制幸运数字。但直接转字符串再计数（`bitset<32>.to_string()` + 遍历）存在冗余内存分配与非必要字符处理；而逐位右移配合 `n & 1` 统计虽高效，却需额外计算位宽以判断是否为偶数长度——若忽略这点（如将 5=101₂ 错判为“2个1+1个0”），会误判。如何在 O(log n) 时间、O(1) 空间内，**不依赖字符串/STL容器、避免前导零干扰、且正确处理边界（如 n=1→"1"）**，实现高鲁棒性的判断？尤其在嵌入式或高频调用场景下，如何进一步通过位运算技巧（如 `__builtin_popcount` 与 `__builtin_clz` 组合）常数级优化？

Answer 1

```html

一、问题本质剖析：什么是“二进制幸运数字”？

“二进制幸运数字”并非标准数论概念，而是典型算法面试与嵌入式位操作场景中构造的约束性判定问题。其数学定义为：

• 设正整数 n > 0，其规范二进制表示为 bk−1bk−2…b0（k = ⌊log₂n⌋ + 1，且 bk−1 = 1）；
• 要求：count_ones(n) == count_zeros_in_significant_bits(n)，即有效位（不含前导零）中 0 的个数 = 1 的个数；
• 推论：总有效位数 k 必须为偶数（因 #1 + #0 = k，且 #1 = #0 ⇒ k = 2×#1），故 k ∈ {2,4,6,…}。

边界关键点：n = 1 → "1" → k=1（奇数）→ #0=0 ≠ #1=1 → ❌ 非幸运数字；n = 9 → "1001" → k=4, #1=2, #0=2 → ✅。

二、常见错误实现与性能陷阱

方法	时间复杂度	空间复杂度	主要缺陷
bitset<32>(n).to_string() + 遍历	O(1)（固定32位）	O(1)但含隐式分配	字符串构造开销大；含27个前导零（如 n=9 → "00000000000000000000000000001001"），需额外跳过；不可移植至裸机环境
右移循环 while(n) { cnt += n&1; n >>= 1; }	O(log n)	O(1)	丢失位宽信息！无法区分 5 (101₂) 和 10 (1010₂) —— 前者误算为3位中#0=1，实则#0=0（无填充）

根本矛盾在于：**计数必须锚定在“最高置位位置”，而非数值本身长度**。未显式获取位宽，一切计数均无效。

三、基础正确解法：手算位宽 + 双计数（O(log n)/O(1)）

核心思想：先用 while 确定最高位索引 k（即有效位数），再遍历 0 到 k−1 位分别统计：

bool isBinaryLucky(uint32_t n) {
  if (n == 0) return false; // 题设隐含 n ≥ 1
  uint32_t k = 0, t = n;
  while (t) { k++; t >>= 1; }        // k = floor(log2(n)) + 1
  if (k & 1) return false;           // 奇数位数直接排除
  uint32_t ones = 0;
  for (uint32_t i = 0; i < k; ++i) {
    ones += (n >> i) & 1;
  }
  return ones * 2 == k; // #0 = k - #1 == #1 ⇒ #1 == k/2
}

该实现满足所有硬性约束：无字符串、无STL、O(log n) 时间、O(1) 空间、正确处理 n=1（k=1→奇数→false）。

四、工业级优化：GCC内置函数常数级加速

在 x86/ARM GCC/Clang 环境下，可利用硬件指令直取关键元数据：

• __builtin_clz(n)：返回前导零个数（32位下，对 n=9 返回 28）→ 有效位宽 k = 32 − __builtin_clz(n)；
• __builtin_popcount(n)：返回 1 的个数（单周期指令，x86 POPCNT）；
• 二者组合可在 常数时间 O(1) 完成判定（忽略分支预测延迟）。

graph TD
  A[输入 n] --> B{ n == 0 ? }
  B -->|Yes| C[return false]
  B -->|No| D[k = 32 - __builtin_clz n]
  D --> E{k % 2 != 0 ?}
  E -->|Yes| F[return false]
  E -->|No| G[ones = __builtin_popcount n]
  G --> H{ones == k / 2 ?}
  H -->|Yes| I[return true]
  H -->|No| J[return false]

五、嵌入式兼容方案与可移植增强

对于无 __builtin_* 的编译器（如某些 ARM Keil 或裸机 GCC），提供查表+分治备选：

• 预计算 0–255 的 popcount 表（256B ROM）；
• 用 __builtin_clz 替代方案：二分查找最高位（4次比较搞定32位）；
• 终极可移植宏：#define BIT_WIDTH(x) ((x) <= 1 ? 1 : 1 + BIT_WIDTH((x)>>1))（递归展开为常量表达式，C++14 constexpr 友好）。

高频调用时建议：将函数声明为 inline __attribute__((always_inline))，并启用 -mpopcnt 编译选项。

六、验证与边界测试用例集

n	二进制	k	#1	#0	isLucky?
1	1	1	1	0	false
3	11	2	2	0	false
9	1001	4	2	2	true
10	1010	4	2	2	true
12	1100	4	2	2	true
15	1111	4	4	0	false
85	1010101	7	4	3	false（奇数位）

覆盖了最小值、临界偶/奇位、全1/交替模式等典型路径，确保鲁棒性。

```