2025-12-28：位计数深度为 K 的整数数目Ⅰ。用go语言，给定两个正整数 n 和 k。对任意正整数 x，构造数列 a0 = x，ai+1 = f(ai)，其中 f(y) 表示 y 的二进制表示中 1 的个数（例如 f(7)=3，因为 7 的二进制是 111）。反复应用 f 后，序列必然会落到 1。定义 x 的“二进制1的迭代次数”为使得 ad = 1 的最小非负整数 d（例如 x=7 的序列为 7→3→2→1，因此迭代次数为 3）。

问题是：在区间 [1, n] 内，有多少个正整数的这种迭代次数恰好等于 k？返回该数量。

1 <= n <= 1000000000000000。

0 <= k <= 5。

输入: n = 4, k = 1。

输出: 2。

解释:

在范围 [1, 4] 中，以下整数的 popcount-depth 恰好等于 1：

x	二进制	序列
2	10	2 → 1
4	100	4 → 1

因此，答案是 2。

题目来自力扣3621。

🔢 问题理解与核心思路

题目要求统计区间 [1, n] 内，有多少个正整数 x 的“位计数深度”（即不断计算其二进制中1的个数，直到结果为1所需的迭代次数）恰好等于 k。

核心解决思路是：

1. 预处理深度映射：对于任意一个数，其深度只与它二进制表示中1的个数有关。我们可以预先计算出，对于含有 i 个1的数，它的深度是多少。
2. 统计目标数字：利用数位动态规划，统计在 [1, n] 范围内，二进制表示中1的个数恰好为 i 的数字有多少个。将这些数字中深度等于 k 的计数累加，即为最终答案。

📝 算法步骤详解

步骤 1: 特殊情况处理

• 如果 k == 0，根据题目定义，只有深度为0的数满足条件，这意味着序列从一开始就是1。在区间 [1, n] 中，只有 x=1 满足条件（因为 f(1)=1），所以直接返回 1。

步骤 2: 将 n 转化为二进制字符串

• 将输入的整数 n 转换为它的二进制字符串表示，例如 n=4 得到字符串 "100"。这样做是为了方便后续的数位DP处理，可以逐位确定数字。

步骤 3: 预处理深度关系

• 创建一个数组 f，f[i] 表示一个二进制表示中有 i 个1的数字，它的位计数深度是多少。
• 计算方式利用了递归关系：一个数的深度，等于它进行一次 popcount 操作后得到的那个数的深度再加1。即 f[i] = f[bits.OnesCount(i)] + 1。
• 初始条件是 f[1] = 0，因为数字1的二进制只有一个1，它本身就已经是1，不需要迭代。
• 然后，我们遍历所有可能的1的个数 i（从1到二进制字符串的长度 m），如果 f[i] == k，说明所有恰好有 i 个1的数都满足深度要求，我们需要统计这类数的个数。

步骤 4: 数位动态规划统计数量

• 这是算法的核心部分，目标是统计在 [1, n] 范围内，二进制表示中恰好有 targetOnes 个1的数字的个数（其中 targetOnes 是上一步中找出的那些使深度等于 k 的1的个数）。
• 记忆化DFS：定义一个DFS函数，其参数包括：
  • i: 当前正在处理二进制字符串的第几位（从0开始）。
  • left1: 在剩余的位数中，还需要放置多少个1。
  • isLimit: 一个布尔值，表示之前确定的位是否完全和 n 的对应位一致。如果为真，则当前位最大只能取 n 在该位的值（0或1）；如果为假，则当前位可以自由取0或1。
• DFS过程：
  1. 到达终点：如果已经处理完所有位 (i == m)，则检查是否恰好用完了所需的1的个数 (left1 == 0)。如果是，则找到一個有效数字，返回1；否则返回0。
  2. 记忆化加速：如果当前状态不受上限限制 (isLimit 为假)，并且这个状态 (i, left1) 之前已经计算过，则直接返回缓存的结果，避免重复计算。
  3. 确定当前位选择范围：根据 isLimit 确定当前位能选择的最大数字 up。
  4. 枚举与统计：尝试在当前位放入 d（0或1），但不能超过 up，并且放入1的总数不能超过 left1。将后续状态的结果累加。
• 通过调用 dfs(0, targetOnes, true) 启动统计过程。

步骤 5: 汇总结果

• 对所有满足 f[i] == k 的 i，调用数位DP统计出二进制中恰好有 i 个1的数字个数，并将这些个数累加，得到最终答案。

⏱️ 复杂度分析

• 时间复杂度：O(log²n)。

  1. 预处理深度数组 f 的时间复杂度为 O(log n)，因为 n 的二进制长度 m 约为 log₂n。
  2. 数位DP是主要开销。DP状态数量由“当前处理到的位置”和“剩余需要的1的个数”决定，规模为 O(m * m) = O(log²n)。每个状态的计算是常数时间。因此，总时间复杂度为 O(log²n)。

• 空间复杂度：O(log²n)。
  空间消耗主要来自数位DP的记忆化数组 memo，其大小也是 O(m * m) = O(log²n)。深度数组 f 等辅助空间为 O(log n)，因此总空间复杂度为 O(log²n)。

Go完整代码如下：

package main

import (
	"fmt"
	"math/bits"
	"strconv"
)

func popcountDepth(n int64, k int) (ans int64) {
	if k == 0 {
		return 1
	}

	// 注：也可以不转成字符串，下面 dfs 用位运算取出 n 的第 i 位
	// 但转成字符串的通用性更好
	s := strconv.FormatInt(n, 2)
	m := len(s)
	if k == 1 {
		return int64(m - 1)
	}

	memo := make([][]int64, m)
	for i := range memo {
		memo[i] = make([]int64, m+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}

	var dfs func(int, int, bool) int64
	dfs = func(i, left1 int, isLimit bool) (res int64) {
		if i == m {
			if left1 == 0 {
				return 1
			}
			return
		}
		if !isLimit {
			p := &memo[i][left1]
			if *p >= 0 {
				return *p
			}
			defer func() { *p = res }()
		}

		up := 1
		if isLimit {
			up = int(s[i] - '0')
		}
		for d := 0; d <= min(up, left1); d++ {
			res += dfs(i+1, left1-d, isLimit && d == up)
		}
		return
	}

	f := make([]int, m+1)
	for i := 1; i <= m; i++ {
		f[i] = f[bits.OnesCount(uint(i))] + 1
		if f[i] == k {
			// 计算有多少个二进制数恰好有 i 个 1
			ans += dfs(0, i, true)
		}
	}
	return
}

func main() {
	const n = 4
	const k = 1
	result := popcountDepth(n, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from functools import lru_cache

def popcount_depth(n: int, k: int) -> int:
    if k == 0:
        return 1
    
    s = bin(n)[2:]
    m = len(s)
    if k == 1:
        return m - 1
    
    # 记忆化搜索
    @lru_cache(None)
    def dfs(i: int, left1: int, is_limit: bool) -> int:
        if i == m:
            return 1 if left1 == 0 else 0
        
        if not is_limit:
            # 非限制状态下可以使用记忆化
            if dfs_cache[i][left1] != -1:
                return dfs_cache[i][left1]
        
        up = 1 if not is_limit else int(s[i])
        res = 0
        for d in range(min(up, left1) + 1):
            res += dfs(i + 1, left1 - d, is_limit and d == up)
        
        if not is_limit:
            dfs_cache[i][left1] = res
        return res
    
    # 预处理 f[i] = 将 i 变换到 1 需要的步数
    f = [0] * (m + 1)
    for i in range(1, m + 1):
        f[i] = f[i.bit_count()] + 1
    
    ans = 0
    for i in range(1, m + 1):
        if f[i] == k:
            # 初始化记忆化数组
            dfs_cache = [[-1] * (m + 1) for _ in range(m)]
            ans += dfs(0, i, True)
    
    return ans

if __name__ == "__main__":
    n = 4
    k = 1
    result = popcount_depth(n, k)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

class Solution {
private:
    long long dfs(int i, int left1, bool isLimit, int m, const string& s,
                  vector<vector<long long>>& memo) {
        if (i == m) {
            return left1 == 0 ? 1 : 0;
        }

        if (!isLimit && memo[i][left1] != -1) {
            return memo[i][left1];
        }

        int up = isLimit ? (s[i] - '0') : 1;
        long long res = 0;

        for (int d = 0; d <= min(up, left1); d++) {
            res += dfs(i + 1, left1 - d, isLimit && d == up, m, s, memo);
        }

        if (!isLimit) {
            memo[i][left1] = res;
        }
        return res;
    }

public:
    long long popcountDepth(long long n, int k) {
        if (k == 0) {
            return 1;
        }

        // 将n转换为二进制字符串
        string s;
        while (n > 0) {
            s = char('0' + (n & 1)) + s;
            n >>= 1;
        }
        int m = s.size();

        if (k == 1) {
            return m - 1;
        }

        // 计算f数组
        vector<int> f(m + 1, 0);
        for (int i = 1; i <= m; i++) {
            f[i] = f[__builtin_popcount(i)] + 1;
        }

        long long ans = 0;

        // 对每个满足f[i]==k的i进行计算
        for (int i = 1; i <= m; i++) {
            if (f[i] == k) {
                // 为每个i创建新的记忆化数组
                vector<vector<long long>> memo(m, vector<long long>(m + 1, -1));
                ans += dfs(0, i, true, m, s, memo);
            }
        }

        return ans;
    }
};

int main() {
    long long n = 4;
    int k = 1;

    Solution solution;
    long long result = solution.popcountDepth(n, k);
    cout << result << endl;

    return 0;
}