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

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

```python
class Solution:
def countBinaryPalindromes(self, n: int) -> int:
if n == 0:
return 1

# 获取 n 的二进制位数（不含前导零）
def get_binary_length(x: int) -> int:
length = 0
while x > 0:
x >>= 1
length += 1
return length

count = 1 # 0 是回文数
m = get_binary_length(n)

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

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

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

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

while left > 0:
palindrome = (palindrome << 1) + (left & 1)
left >>= 1

if palindrome <= n:
count += 1

return count
```

核心思路

步骤 说明
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)`