求0到k中与x按位与为0的整数个数（需超O(k)高效实现）

问题分析 #

我们需要找出 0 ≤ i ≤ k 中满足 i & x == 0 的整数个数。这个条件等价于：i的二进制位上，所有x为1的位置，i必须是0——也就是说，i只能在x的二进制为0的位上自由取值。

解决方案 #

这里提供两种方案，其中方案二完全满足「时间复杂度优于O(k)、支持多次调用」的要求，方案一则利用题目给出的|k-x| ≤ 1e6约束做了针对性优化。

方案一：利用约束的快速计算

因为k和x的差距不超过1e6，我们可以拆分计算：

1. 计算0到min(k, x)的合法数数量：使用方案二的数位DP方法（避免暴力遍历）。
2. 处理区间差值部分：
   • 若k > x：遍历x+1到k的所有数，统计满足i & x == 0的数量，和第一步结果相加。
   • 若k < x：直接使用第一步的结果即可。

这种方法的时间复杂度为O(32 + 1e6)，单次调用足够高效，适合调用次数不多的场景。

方案二：通用数位DP方法（推荐，支持多次调用）

数位DP可以在O(32)的时间内完成计算（对应32位整数，若处理64位则是O(64)），完全满足多次调用的需求。核心思路是逐位处理k的二进制，同时保证每一步都符合i & x == 0的约束。

代码实现（Python）

def count_valid(k, x):
    # 将k转换为高位在前的二进制数组
    bits = []
    temp = k
    while temp > 0:
        bits.append(temp % 2)
        temp = temp // 2
    bits = bits[::-1]
    n = len(bits)
    
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(pos, tight):
        # 处理完所有位，找到一个合法数
        if pos == n:
            return 1
        
        # 当前位的最大取值：如果tight为True，不能超过k的当前位
        limit = bits[pos] if tight else 1
        total = 0
        
        for bit in range(0, limit + 1):
            # 检查x的当前位：若x该位为1，i的该位必须为0
            x_bit = (x >> (n - 1 - pos)) & 1
            if x_bit == 1 and bit != 0:
                continue
            
            # 更新tight标记：只有当前位取了k的对应位且之前tight，才继续保持tight
            new_tight = tight and (bit == limit)
            total += dp(pos + 1, new_tight)
        
        return total
    
    return dp(0, True)

代码解释

• 二进制转换：将k转为高位在前的二进制数组，方便逐位处理。
• 记忆化递归：dp(pos, tight)表示处理到第pos位时，当前前缀是否严格等于k的前缀（tight为True表示受k的约束），返回从该位开始的合法数总数。
• 约束检查：遍历当前位的可能取值时，若x对应位为1，则i的该位只能取0，否则跳过该取值。
• tight更新：若当前位取了k的对应位且之前处于约束状态，后续位仍受k的约束；否则后续位可以自由取0或1。

测试示例

比如x=3（二进制11），k=5（二进制101），合法的i为0、4，调用count_valid(5,3)会返回2，符合预期。

内容的提问来源于stack exchange，提问作者Tomek Swiecki