def count_pairs(a, b, k):
ans = 0
for i in range(30, -1, -1):
if k >> i & 1:
for j in range(30, -1, -1):
if b >> j & 1:
if i > j:
ans += 1 << (i + j)
else:
if (k >> j & 1) == 0:
ans += 1 << (i + j)
else:
mask = (1 << j) - 1
lo = max(0, (1 << i) - b)
hi = min(1 << i, a)
if hi > lo:
ans += (hi - lo) * (b & mask)
lo = max(0, (1 << j) - a)
hi = min(1 << j, b)
if hi > lo:
ans += (hi - lo) * (a & mask)
lo = max(0, k - (1 << j))
hi = min(1 << i, k - (1 << j - 1))
if hi > lo:
ans += (hi - lo) * (1 << j)
break
return ans
首先我们可以考虑暴力的做法，枚举所有的数对(x,y)，判断它们的位与结果是否小于k，时间复杂度为O(a*b)。但是当a和b较大时，这个做法显然不可取。
因此我们考虑优化这个做法。观察位与的性质，我们可以发现，当x和y二进制下某一位上的数都为1时，它们的位与结果才会为1，否则为0。因此我们只需要找到满足x和y二进制下某一位上的数都为1的最高位i，使得x和y在i位之前的二进制数分别为a和b的前缀，然后判断x和y在i位之后的二进制数的位与结果是否小于k即可。
我们可以用动态规划来实现这个做法。设f[i][0/1][0/1]表示考虑到第i位，x和y在这一位之前的二进制数是否与a和b在这一位上的数相同，是否已达到a和b的上界，当前位与结果是否小于k的方案数。则状态转移方程为：
f[i][0][0] = f[i-1][0][0] + f[i-1][1][0] // a和b在i位上的数都为0
f[i][1][0] = f[i-1][1][0] // a和b在i位上的数都为1，且未超过上界
f[i][1][1] = f[i-1][0][1] + f[i-1][1][1] // a和b在i位上的数都为1，且超过上界
最终的答案即为f[31][0][1] + f[31][1][1]，其中31表示二进制下最高位的位数。
下面是代码实现：