给定三个整数 a,b,k ，计算满足 0<=x<a 和 0<=y<b 的位与结果小于 k（即(x&y)<k）的有序数对(x,y)的个数

Question

给定三个整数 a,b,k ，计算满足 0<=x<a 和 0<=y<b 的位与结果小于 k（即(x&y)<k）的有序数对(x,y)的个数。（动态规划问题

Answer 1

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