🤖 AI总结
主题
力扣3954题：求区间内与n按位与为0的正整数之和。
摘要
通过前缀差分与二进制逐位扫描，利用自由位快速计算区间内与n按位与为0的正整数之和。
关键信息
- 1 用前缀差分将区间求和转为两个前缀之差。
- 2 按二进制从高位扫描，利用自由位一次性计算整块和。
- 3 时间复杂度O(log(n+k))，空间复杂度O(1)。
2026-09-13：区间内的兼容数字之和Ⅰ。用go语言，有两个整数 n、k。现在要从所有正整数里挑出满足下面两个要求的数 x：
第一，x 与 n 相差不能超过 k，也就是说，n 与 x 的差的绝对值要小于或等于 k。
第二，把 n 和 x 做按位与运算后，结果必须是 0。换句话说，在二进制形式下，n 和 x 不能在同一个位置上同时都是 1。
请找出全部满足条件的 x，并把这些 x 加在一起，返回总和。
其中，按位与运算就是符号 & 所表示的运算；两个整数之间的绝对差，就是较大的数减去较小的数。
1 <= n <= 100。
1 <= k <= 100。
输入： n = 2, k = 3。
输出： 10。
解释：
兼容整数为：
x = 1，因为 abs(2 – 1) = 1 且 2 & 1 = 0。
x = 4，因为 abs(2 – 4) = 2 且 2 & 4 = 0。
x = 5，因为 abs(2 – 5) = 3 且 2 & 5 = 0。
因此，答案为 1 + 4 + 5 = 10。
题目来自力扣3954。
一、第一步：把”区间求和”改成”两个前缀之差”
题目要求的是闭区间[n-k, n+k]内、且与n按位与为 0 的正整数x之和。
但正整数不能小于 1，所以左端点要兜底：
• 右端点high = n + k
• 左端点low = max(n-k, 1)（当n-k < 1时从 1 开始）
接着定义一个前缀函数F(N)：
F(N) = 所有满足 0 ≤ x < N 且 (x & n) == 0 的 x 之和。
这里刻意用左闭右开[0, N)，有两个好处：
1. 区间拼接天然无缝：[low, high]的和 =F(high+1) - F(low)。注意右端点要+1，因为F不含右端点。
2. 把0也算进去了，但0 & n == 0且它对和的贡献是 0，所以丝毫不影响结果，省掉了”排除 0″的特判。
于是原问题被拆成两次calc调用再相减，这就是sumOfGoodIntegers里那一行在做的事。
二、第二步：F(N)要怎么算——把数字当二进制串，从高位往低位扫
暴力做法是枚举0 ~ N-1每个数判一次，复杂度O(N)。这份代码的思路是整体统计：
把x和N都看成二进制串，从最高位到最低位一位一位比。扫描时始终维护这样一个状态：
当前的”前缀”（比当前位更高的那些位）已经和 N 完全一样，也就是说还没决出大小，贴着上界走。
对某一位i：
•如果 N 的第 i 位是 0：x这一位只能填 0（填 1 就超过 N 了），继续贴着上界，什么都不用统计。
•如果 N 的第 i 位是 1：出现分叉，产生两支：
•分支 A（”变小”支）：x这一位填0。此时x < N已经板上钉钉（更高位都相同，这一位 N 是 1、x 是 0），后面所有低位可以随便填（只要满足与 n 的与为 0）。这一整块数可以一次性用公式算出来，不用逐个枚举。
•分支 B（”紧贴”支）：x这一位填1，继续保持和 N 相等的前缀，进入下一位继续扫描。
为什么这样不重不漏？因为任意一个满足x < N的数，它与 N 的二进制比较中，必定存在唯一的一个最高位j，使得x的第j位是 0、N的第j位是 1（更高位全相同）。扫描到i = j时，走”分支 A”正好把它收进去；而它在其它位上走的是紧贴支，不会产生贡献。所以每个合法数被且只被统计一次。
三、第三步：引入”自由位”——把约束(x & n) == 0翻译掉
条件x & n == 0等价于：凡是 n 的二进制为 1 的位，x 必须为 0；而 n 为 0 的位，x 填 0、填 1 都无所谓。
所以代码定义：
• 取m = N的二进制位数（即bits.Len(N)），构造 m 位全 1 的掩码2^m - 1；
•freeMask = (2^m - 1) &^ n：在 m 位范围内，把所有 n 为 1 的位清掉，剩下的 1 就是”自由位”（可 0 可 1 的位）；
•freeCnt = freeMask 中 1 的个数，也就是自由位的个数。
有了自由位，”分支 A”里”后面低位随便填”就变成了一个可数的问题：低位共有freeCnt个自由位，每个 0/1 任选，一共2^freeCnt个不同的后缀。
四、第四步：分支 A 一次性算出整块的和
当在第i位走分支 A（N 该位为 1、x 该位填 0）时，所有这类 x 都长成：
x = 高位固定前缀 prefix + 低位的自由位任意组合其中prefix是扫描过程中”紧贴支”上已经填了 1 的那些高位拼出来的数值（用一个变量prefix累积，见第六步）。
这2^freeCnt个数的总和可以拆成两部分相加（因为加法可以逐位拆）：
1）前缀部分的贡献
每个数都包含同一个prefix，一共有2^freeCnt个数：
贡献 = prefix × 2^freeCnt，代码写成 prefix << freeCnt。
2）后缀（自由位）部分的贡献
单独看某一个自由位 b：在所有2^freeCnt种组合中，它有恰好一半即2^(freeCnt-1)种情况取 1，所以这一位的贡献是2^b × 2^(freeCnt-1)。
把所有自由位加起来：(所有自由位的 2^b 之和) × 2^(freeCnt-1)。而”所有自由位的2^b之和”恰好就是freeMask这个整数本身（因为自由位之间不重叠，二进制加法不进位）。
贡献 = freeMask × 2^(freeCnt-1)，代码写成 freeMask * (1 << freeCnt >> 1)。这个式子还天然处理了 freeCnt = 0 的边界：1<<0>>1 = 0，即没有自由位时后缀贡献为 0。
两部分相加，就得到了分支 A 这一整块的总和，一次加进res。
五、第五步：每一轮开头对自由位集合的”瘦身”
循环体第一件事是：
如果 n 的第 i 位是 0（说明第 i 位本来算在自由位里），就把 freeCnt 减 1，并把这一位从 freeMask 中剔除。
用意是：进入第i位的处理时，freeMask / freeCnt必须只描述”当前位 i 以下（更低位）”的自由位。因为第i位本身是”现在要决定填 0 还是填 1″的那一位，它一旦走分支 A 就已经被固定成 0 了，不能算进”后面能随便填的自由位”里。
如果n的第i位是 1，那这一位压根不在freeMask里，自然不需要剔除。
六、第六步：分支 B（继续紧贴）的处理与循环终止
走完分支 A 后，还要考虑分支 B（x这一位填 1，继续贴着 N 走）。这里有一个硬约束：
只有 n 的第 i 位是 0 时，x 这一位才能填 1。
• 如果n的第i位是 0：可以填 1，于是把这一位并入前缀（prefix |= 1 << i），继续下一位。
• 如果n的第i位是 1：x这一位必须是 0，而 N 这一位是 1，说明紧贴支不可能再产生任何x ≥ N的合法解了——所有合法解都已经在刚才的分支 A 里被算完了，直接break结束。
关于循环自然结束（一直没 break）：扫描完第 0 位后，紧贴支最终得到的那个数是x = N本身。由于F(N)的区间是[0, N)，N自己不该被算进去，而代码恰好从头到尾只在”分支 A”（x某位填 0 而 N 填 1）时才累加，紧贴支走到最后从不额外加N。所以左闭右开的语义被天然满足了，不需要任何收尾特判。
七、完整走一遍样例：n = 2, k = 3
1）确定区间与差分low = max(2-3, 1) = 1，high = 2+3 = 5，答案 =F(6) - F(1)。
2）算F(6)（N = 6 = 110₂，n = 2 = 010₂）
•m = 3（6 需要 3 位），freeMask = 111₂ &^ 010₂ = 101₂ = 5，freeCnt = 2，prefix = 0，res = 0。
位 i
瘦身后的 freeMask / freeCnt
N 该位
分支 A（x 填 0）
分支 B
i=2
n 该位为 0 → 剔除第 2 位，freeMask=1(即 001₂)，freeCnt=1
是 1
前缀贡献0<<1 = 0；后缀贡献1 × (2^1/2) = 1。即数集 {000,001} = {0,1}，和 = 1。res=1
n 该位为 0，可填 1 → prefix = 4
i=1
n 该位为 1 → 不变，freeMask=1，freeCnt=1
是 1
前缀贡献4<<1 = 8；后缀贡献1 × 1 = 1。即数集 {100,101} = {4,5}，和 = 9。res=10
n 该位为 1 → 不能填 1，break
F(6) = 10，对应合法数 {0, 1, 4, 5}，和 = 0+1+4+5 = 10。✓
3）算F(1)（N = 1 = 1₂）
•m = 1，freeMask = 1 &^ 2 = 1，freeCnt = 1。
• i=0：n 该位为 0 → 剔除后 freeMask=0，freeCnt=0。N 该位是 1 → 分支 A 贡献0<<0 = 0与0 × 0 = 0，res 仍为 0；分支 B 令 prefix=1，循环结束（x=1 本身不计入）。
•F(1) = 0（小于 1 的只有 0）。
4）相减：10 - 0 = 10。
与样例输出一致：兼容数是1、4、5，和为10。✓
八、复杂度分析
设M = high + 1 = n + k + 1，m = bits.Len(M) = ⌊log₂M⌋ + 1，也就是数字的二进制位数。
•时间复杂度：O(log(n + k))
每次calc内部只有一个从m-1到0的单重循环，循环体里全都是 O(1) 的位运算和整数四则运算（移位、按位与、异或、加法、乘法），没有嵌套、没有递归、没有枚举所有数。调用两次calc，所以总时间是2 × O(m) = O(log(n+k))。对比一下：暴力枚举[low, high]需要 O(k) 次判断，而这个方法与 k 的大小无关，只和数字的二进制位数有关——即使 n、k 大到 10⁹ 甚至 10¹⁸，也只要循环 30～60 次（当然在 Go 的 int 下要注意溢出，本题 n,k ≤ 100 完全无压力）。
•额外空间复杂度：O(1)
全程只用了m、freeMask、freeCnt、prefix、res、i这几个整型变量（外加sumOfGoodIntegers里的low、high），没有任何数组、哈希表、递归栈或动态分配的空间，占用不随输入规模变化。
一句话总结：先用前缀差分把闭区间变成两个”小于 N”的前缀问题；再按二进制从高位扫到低位，借助”自由位”把与n的与为 0 这个约束转化成”低位有多少位可任意填”；每当上界某位为 1 时，就把”该位填 0、低位全自由”的那一整块数用prefix × 2^c + freeMask × 2^(c-1)一次性算出，从而在 O(log) 时间和 O(1) 空间内得到答案。
Go完整代码如下：
package main
import (
"fmt"
"math/bits"
)// 计算小于 high 的正整数中，AND n 等于 0 的数之和
func calc(high, n int) (res int) {
m := bits.Len(uint(high))
freeMask := (1< 1 ) &^ n
freeCnt := bits.OnesCount( uint (freeMask))
prefix := 0
for i := m - 1 ; i >= 0 ; i-- {
if n>>i& 1 == 0 {
freeCnt--
freeMask ^= 1 << i
}
if high>>i& 1 > 0 {
// 这一位填 0
res += prefix << freeCnt // 前缀的贡献：后面 freeCnt 个位置，0 和 1 随便填
res += freeMask * ( 1 << freeCnt >> 1 ) // 后缀的贡献：每个 free 位置固定为 1 时，其余 freeCnt-1 个位置 0 和 1 随便填
// 这一位填 1，继续计算
if n>>i& 1 > 0 { // 这一位不能填 1
break
}
prefix |= 1 << i
}
}
return
}
func sumOfGoodIntegers(n, k int) int {
low := max(n-k, 1 )
high := n + k
return calc(high+ 1 , n) - calc(low, n)
}
func main() {
n := 2
k := 3
result := sumOfGoodIntegers(n, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def calc(high, n):
res = 0
m = high.bit_length()
free_mask = ((1 << m) - 1) & ~n
free_cnt = bin(free_mask).count("1")
prefix = 0
for i in range(m - 1, -1, -1):
if ((n >> i) & 1) == 0:
free_cnt -= 1
free_mask ^= 1 << i
if ((high >> i) & 1) > 0:
# 这一位填 0
res += prefix << free_cnt
res += free_mask * ((1 << free_cnt) >> 1)
# 这一位填 1，继续计算
if ((n >> i) & 1) > 0:
break
prefix |= 1 << i
return res
def sumOfGoodIntegers(n, k):
low = max(n - k, 1)
high = n + k
return calc(high + 1, n) - calc(low, n)
def main():
n = 2
k = 3
result = sumOfGoodIntegers(n, k)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;
// 计算小于 high 的正整数中，AND n 等于 0 的数之和
long long calc(long long high, long long n) {
if (high <= 0) return 0;
// 计算 high 的二进制位数
int m = 0;
unsigned long long uh = high;
m = 64 - __builtin_clzll(uh);
// 构造掩码：低 m 位全为 1
unsigned long long mask = (m == 64) ? ~0ULL : ((1ULL << m) - 1);
// freeMask 表示在 n 中为 0 的位（即可以自由填 1 的位）
unsigned long long freeMask = mask & ~(unsigned long long)n;
int freeCnt = __builtin_popcountll(freeMask);
long long res = 0;
long long prefix = 0;
for (int i = m - 1; i >= 0; i--) {
// 如果 n 的第 i 位是 0，则这一位是自由的，从 freeMask 中移除
if (((n >> i) & 1) == 0) {
freeCnt--;
freeMask ^= (1ULL << i);
}
if (((high >> i) & 1) > 0) {
// 当前位填 0 的情况
res += prefix << freeCnt;
res += (long long)freeMask * ((1ULL << freeCnt) >> 1);
// 当前位尝试填 1
if (((n >> i) & 1) > 0) {
// n 的这一位是 1，不能填 1，直接结束
break;
}
prefix |= (1LL << i);
}
}
return res;
}
long long sumOfGoodIntegers(long long n, long long k) {
long long low = max(n - k, 1LL);
long long high = n + k;
return calc(high + 1, n) - calc(low, n);
}int main() {
long long n = 2;
long long k = 3;
long long result = sumOfGoodIntegers(n, k);
cout << result << endl;
return 0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
