应使用按位分析的数学方法而非暴力遍历，时间复杂度从O(N log N)降至O(log N)；以N=2314百位为例，拆解为high=2、cur=3、low=14、digit=100，依cur值分三类计算1出现次数，C++中需用long long防溢出。
直接结论：别用暴力遍历，用数位DP或数学归纳法
暴力循环每个数、转字符串再统计 1 的个数，时间复杂度是 O(N log N)，N 超过 10⁷ 就明显卡顿。实际工程中 N 动辄 10⁹，必须用 O(log N) 的数学方法——核心是按位分析每一位上数字 1 出现的规律。
关键思路：按位拆解，分 high / cur / low 三段计算
以 N = 2314 为例，当前看百位（即第 3 位，从右往左数，个十百千…），该位数字是 3，此时把它拆成：
– high = 2（高位部分：2314 / 1000 = 2）
– cur = 3（当前位：(2314 / 100) % 10 = 3）
– low = 14（低位部分：2314 % 100 = 14）
– digit = 100（当前位权值）
那么百位上出现 1 的总次数为：
– 若 cur == 0：贡献是 high * digit
– 若 cur == 1：贡献是 high * digit + low + 1
– 若 cur > 1：贡献是 (high + 1) * digit
这个公式本质是统计：在 0~N 中，有多少个数的百位恰好是 1。它把所有可能组合归为三类，避免枚举。
C++ 实现要点：注意整型溢出和边界条件
用 long long 存 digit 和中间结果，因为当 N 接近 INT_MAX 时，digit 可能到 10¹⁰，int 会溢出。
循环终止条件是 digit ，不是 <code>digit —— 否则最高位被跳过。<br>每次迭代更新顺序必须是：<code>high = n / (digit * 10)，cur = (n / digit) % 10，low = n % digit。
立即学习“C++免费学习笔记（深入）”；
参考片段：
long long countDigitOne(long long n) {
if (n <= 0) return 0;
long long count = 0, digit = 1;
while (digit <= n) {
long long high = n / (digit * 10);
long long cur = (n / digit) % 10;
long long low = n % digit;
if (cur == 0) count += high * digit;
else if (cur == 1) count += high * digit + low + 1;
else count += (high + 1) * digit;
digit *= 10;
}
return count;
}
容易忽略的坑：N=0、负数、以及 digit 增长越界
题目说“1 到 N”，但函数常被误用于 N=0 或负数输入，务必前置校验：if (n <br><code>digit 从 1 开始，乘 10 后可能超过 LLONG_MAX / 10，但只要循环条件写成 digit ，且 <code>n 是非负 long long，就不会触发溢出——因为 digit 第一次超限时，循环已退出。
另一个隐性错误：用 int digit = 1，后续 digit *= 10 在 32 位环境里很快溢出为负，导致无限循环。
真正难的不是推导公式，而是把 high/cur/low 的划分逻辑和整数除法取整特性对齐——C++ 中 / 对正数就是向下取整，这点刚好契合需求；一旦混入负数，整个逻辑就崩了。
