第一题还可以参考lc233 数字1的个数,按位统计1的个数,然后加起来。或许可以进一步减小时间复杂度。 public static int countByBit(int n) { if (n == 1) return 1; int t = n; int cnt = 0; if ((t & 1) == 1) {//number of 1 in the lowest digit t = t >> 1; cnt += (t + 1); } else { t = t >> 1; cnt +=t; } int mask = 1; while (t > 1) { int prev = t >> 1; int after = n & mask; if ((t & 1) == 1) { cnt += (prev + 1) * (after + 1); } else { cnt += prev * (after + 1); } t = prev; mask |= (mask << 1); } cnt += (n & mask) + 1;//number of 1 in the highest digit return cnt; }