Kimi LeetCode 3677. 统计二进制回文数字的数目 Rust实现

这是可以直接提交到 LeetCode 的完整 Rust 实现：

```rust
impl Solution {
pub fn count_binary_palindromes(n: i64) -> i32 {
if n == 0 {
return 1;
}

let mut count: i64 = 1; // 0 是回文数

// 获取 n 的二进制位数（不含前导零）
let m = 64 - n.leading_zeros() as i32;

// 1. 统计二进制位数小于 m 的所有回文数
// 长度为 i 的二进制回文数个数 = 2^((i-1)/2)
// 首位必须是 1，左半部分（含中间位）有 (i-1)/2 个自由位
for i in 1..m {
count += 1i64 << ((i - 1) / 2);
}

// 2. 统计二进制位数等于 m 且不超过 n 的回文数
let mid = m / 2; // 左半部分的长度（奇数时包含中间位）

// 从左半部分的最高位向中间遍历
// 如果 n 的某一位是 1，我们可以把它改成 0，剩下的位可以任意填
for i in (mid..=m - 2).rev() {
if (n >> i) & 1 == 1 {
// 当前位填 0（比 n 小），剩余可自由填的位数产生的回文数个数
count += 1i64 << (i - mid);
}
}

// 3. 检查 n 本身（或其左半部分生成的回文数）是否 <= n
let mut left = n >> mid; // 提取左半部分（含中间位，如果是奇数长度）
let mut palindrome = if m % 2 != 0 { left >> 1 } else { left };

// 将左半部分镜像到右边，构造完整的回文数
while left > 0 {
palindrome = (palindrome << 1) + (left & 1);
left >>= 1;
}

if palindrome <= n {
count += 1;
}

count as i32
}
}
```

核心思路

步骤 说明
1. 特判 0 `0` 的二进制是 `"0"`，是回文数
2. 统计短位数回文 长度为 `i` 的二进制回文数，首位必为 1，左半部分（含中间位）有 `(i-1)/2` 个自由位，共 `2^((i-1)/2)` 个
3. 统计同位数回文 从高位到低位遍历 `n` 的左半部分。遇到 `1` 时，将其改为 `0`，剩余自由位可任意填，累加方案数
4. 检查 n 本身 用 `n` 的左半部分构造回文数，若 ≤ n 则计数 +1

复杂度

- 时间：`O(log n)`，只遍历 `n` 的二进制位
- 空间：`O(1)`