企业官网建设流程全解析

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。

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完整代码如下：

packagemainimport("fmt""math/bits")// 计算小于 high 的正整数中，AND n 等于 0 的数之和funccalc(high,nint)(resint){m:=bits.Len(uint(high))freeMask:=(1<<m-1)&^n freeCnt:=bits.OnesCount(uint(freeMask))prefix:=0fori:=m-1;i>=0;i--{ifn>>i&1==0{freeCnt--freeMask^=1<<i}ifhigh>>i&1>0{// 这一位填 0res+=prefix<<freeCnt// 前缀的贡献：后面 freeCnt 个位置，0 和 1 随便填res+=freeMask*(1<<freeCnt>>1)// 后缀的贡献：每个 free 位置固定为 1 时，其余 freeCnt-1 个位置 0 和 1 随便填// 这一位填 1，继续计算ifn>>i&1>0{// 这一位不能填 1break}prefix|=1<<i}}return}funcsumOfGoodIntegers(n,kint)int{low:=max(n-k,1)high:=n+kreturncalc(high+1,n)-calc(low,n)}funcmain(){n:=2k:=3result:=sumOfGoodIntegers(n,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defcalc(high,n):res=0m=high.bit_length()free_mask=((1<<m)-1)&~n free_cnt=bin(free_mask).count("1")prefix=0foriinrange(m-1,-1,-1):if((n>>i)&1)==0:free_cnt-=1free_mask^=1<<iif((high>>i)&1)>0:# 这一位填 0res+=prefix<<free_cnt res+=free_mask*((1<<free_cnt)>>1)# 这一位填 1，继续计算if((n>>i)&1)>0:breakprefix|=1<<ireturnresdefsumOfGoodIntegers(n,k):low=max(n-k,1)high=n+kreturncalc(high+1,n)-calc(low,n)defmain():n=2k=3result=sumOfGoodIntegers(n,k)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<algorithm>#include<climits>usingnamespacestd;// 计算小于 high 的正整数中，AND n 等于 0 的数之和longlongcalc(longlonghigh,longlongn){if(high<=0)return0;// 计算 high 的二进制位数intm=0;unsignedlonglonguh=high;m=64-__builtin_clzll(uh);// 构造掩码：低 m 位全为 1unsignedlonglongmask=(m==64)?~0ULL:((1ULL<<m)-1);// freeMask 表示在 n 中为 0 的位（即可以自由填 1 的位）unsignedlonglongfreeMask=mask&~(unsignedlonglong)n;intfreeCnt=__builtin_popcountll(freeMask);longlongres=0;longlongprefix=0;for(inti=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+=(longlong)freeMask*((1ULL<<freeCnt)>>1);// 当前位尝试填 1if(((n>>i)&1)>0){// n 的这一位是 1，不能填 1，直接结束break;}prefix|=(1LL<<i);}}returnres;}longlongsumOfGoodIntegers(longlongn,longlongk){longlonglow=max(n-k,1LL);longlonghigh=n+k;returncalc(high+1,n)-calc(low,n);}intmain(){longlongn=2;longlongk=3;longlongresult=sumOfGoodIntegers(n,k);cout<<result<<endl;return0;}