BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 17 题

（6 分）方程 $a\times b = (a \operatorname{or} b) \times (a \operatorname{and} b)$，在 $a,b$ 都取 $[0,15]$ 中的整数时，共有（ ）组解。

（$\operatorname{or}$ 表示按位或运算；$\operatorname{and}$ 表示按位与运算）

这道题本质是考察位运算与集合交集并集的关系。拿到题先别急着代入数字，把等式两边展开看看：右边是 (a|b)(a&b)，利用分配律拆开，你会发现它等于 ab + a(a&b) + b(a&b) + (a&b)^2。再对比左边 ab，两边消去后，问题瞬间转化为判断 a(a&b) + b(a&b) + (a&b)^2 是否恒为 0。这直接指向一个核心结论：只有当 a 和 b 至少有一个为 0 时，等式才成立。

很多学生看到 or 和 and 就慌了，觉得要暴力枚举 16×16 种情况，或者试图用代数变形却算错了系数。更隐蔽的坑是选 A 或 B，误以为只要 a 或 b 有一个为 0 就行，却忘了当 a=0 且 b=0 时，a&b=0，等式依然成立，但很多人会漏掉 (0,0) 这组，或者把 a=0 和 b=0 的情况重复计算。还有人会误把 a&b 当成 a+b，导致算出 256 这种离谱答案。

【考点与概念】本题核心是位运算的性质：a|b 表示 a 和 b 的并集（有 1 的位置），a&b 表示交集（同时为 1 的位置）。等式右边 (a|b)(a&b) 可以展开为 ab + a(a&b) + b(a&b) + (a&b)^2。左边是 ab。两边相减得 a(a&b) + b(a&b) + (a&b)^2 = 0。

【思考心法】看到 a(a&b) + b(a&b) + (a&b)^2 = 0，立刻意识到每一项都是非负的（因为 a,b,a&b 都是非负整数）。三个非负数之和为 0，当且仅当每一项都为 0。因此必须同时满足：a(a&b)=0，b(a&b)=0，(a&b)^2=0。显然 (a&b)^2=0 意味着 a&b=0。代入前两项，得到 a·0=0 和 b·0=0，恒成立。所以唯一约束就是 a&b=0。

【计算验证】a&b=0 意味着 a 和 b 没有共同的二进制位为 1。在 [0,15] 范围内，a 和 b 各自有 16 种取值。对于任意固定的 a，b 必须满足 b&a=0。我们可以枚举：当 a=0 时，b 可取 0~15 共 16 个；当 a=1 (0001) 时，b 不能含第 0 位，可取 0,2,4,6,8,10,12,14 共 8 个；当 a=2 (0010) 时，b 不能含第 1 位，同样 8 个；……当 a=15 (1111) 时，b 必须为 0，只有 1 个。

更聪明的做法：总解数 = Σ_{a=0}^{15} (满足 b&a=0 的 b 的个数)。注意到对于每个 a，满足条件的 b 的个数等于 2^{k}，其中 k 是 a 中 0 的位数。a 从 0 到 15，其二进制表示中 0 的位数依次为：a=0(0000)→4 个 0→2^4=16；a=1(0001)→3 个 0→8；a=2(0010)→3 个 0→8；a=3(0011)→2 个 0→4；a=4(0100)→3 个 0→8；a=5(0101)→2 个 0→4；a=6(0110)→2 个 0→4；a=7(0111)→1 个 0→2；a=8(1000)→3 个 0→8；a=9(1001)→2 个 0→4；a=10(1010)→2 个 0→4；a=11(1011)→1 个 0→2；a=12(1100)→2 个 0→4；a=13(1101)→1 个 0→2；a=14(1110)→1 个 0→2；a=15(1111)→0 个 0→1。

把这些数加起来：16+8+8+4+8+4+4+2+8+4+4+2+4+2+2+1 = 146。

【命题视角】命题人喜欢考这种“看似复杂，实则退化”的等式，利用位运算的非负性强制每一项为 0，从而把问题简化为计数 a&b=0 的组合。这种题型在 CSP-J/S 中属于中等偏下难度，但容易因计算繁琐而出错。

【避坑】最容易错的是漏掉 a=0 或 b=0 的情况，或者在枚举时把 a=15 对应的 b=0 算进去却忘了 a=0 时 b=0 已经算过，导致重复或遗漏。还有人会把 a&b=0 误认为 a+b=0，从而只算出 (0,0) 一组，选错 A。

【考频与趋势】根据历年真题统计，位运算相关题目在 CSP-J/S 中每年出现 1~2 次，近五年考频稳定在 1 次/年。本题属于基础位运算 + 计数结合，是高频考点。未来可能继续以类似形式出现，比如扩展到 a,b,c 三个变量，或改变运算为异或等，但核心思路仍是利用非负性逐项归零。

综上，正确答案为 C. 146。