求区间[l, r]内按位与为0的自然数对数量的高效解法

核心思路 #

因为区间长度n = r - l + 1 ≤ 1e6 + 1，可以直接遍历区间内的每个数，对每个数x，快速计算区间内满足x & y = 0的y的数量，最后累加所有结果得到有序数对总数；若需无序数对，因x ≥ 1时x & x = x ≠ 0，直接将有序总数除以2即可。

关键在于高效计算单个x对应的有效y的数量：将问题转化为求[l, r]中满足y & x = 0的数的个数，等价于f(r) - f(l-1)，其中f(n)是[0, n]中满足条件的数的个数，而f(n)可通过数位DP在O(30)时间内完成计算（因1e9的二进制最多30位）。

具体步骤 #

1. 遍历区间内的数 #

无需额外存储数组，直接从l到r逐个遍历每个数x即可，节省空间。

2. 实现f(n)函数：计算[0, n]中与x按位与为0的数的个数 #

采用迭代式数位DP，从最高位到最低位遍历二进制位，维护当前是否严格小于n的前缀（tight标记），统计合法数的数量：

def count_zero_and(n, x):
    if n < 0:
        return 0
    res = 0
    tight = True
    # 遍历1e9范围内的所有二进制位（最高到30位）
    for i in range(30, -1, -1):
        if tight:
            bit_n = (n >> i) & 1
            bit_x = (x >> i) & 1
            if bit_x == 1:
                # y的这一位必须为0，若n的当前位是1，后续可自由取值
                if bit_n == 1:
                    tight = False
                continue
            else:
                # y的这一位可选0或1
                if bit_n == 1:
                    # 取1时，剩余位可自由组合，直接加对应数量
                    res += 1 << i
                    tight = False
        else:
            # 前缀已小于n，只要x当前位为0，剩余位可自由组合
            if ((x >> i) & 1) == 0:
                res += 1 << i
    # 最后检查n本身是否满足条件
    if (n & x) == 0:
        res += 1
    return res

3. 累加每个x的有效数对数量 #

对每个x，计算区间内满足条件的y的数量：

current_cnt = count_zero_and(r, x) - count_zero_and(l-1, x)
total += current_cnt

其中total为有序数对的总数。

4. 得到最终结果 #

• 若要求有序数对（(x,y)和(y,x)视为不同）：结果即为total。
• 若要求无序数对（(x,y)和(y,x)视为同一对）：结果为total // 2（因x≥1时x&x≠0，无重复计数的自对）。

复杂度分析 #

• 时间复杂度：O(n * 30)，其中n ≤ 1e6，总操作约3e7次，在多数编程语言中均可高效完成。
• 空间复杂度：O(1)，无需存储整个区间数组，仅需遍历过程中的临时变量。

优化方向 #

• 统计区间内的数的频率：若区间内存在重复数，只需计算一次该数的current_cnt，再乘以出现频率即可减少重复计算。
• 位运算优化：将数位DP中的分支判断用位运算简化，进一步提升运行速度。

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