对于一个正整数,我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高,这个数就越孤单。那么问题来了,对于给定的[a,b]区间中。最孤单的数字是谁呢?
如果光棍指数相同,最孤单的就是最小的那个数。
第一行一个整数 T (1≤T≤10^4),表示问题数。
接下来 T 行,每行两个整数 a,b (0≤a≤b≤2^31−1)。数据之间用一个空格分隔。
对于每个问题,输出一行 Case x: y,其中 x 是问题编号,从 1 开始,y 是答案
2 0 14 100 1000
Case 1: 7 Case 2: 511
# coding=utf-8 def count_one(x): """统计十进制数x的二进制表示的1的个数""" x_bi_str = bin(x) n = 0 for c in x_bi_str[2:]: if c == "1": n += 1 return n, len(x_bi_str) - 2 def all_ones(x): """判断某数的二进制是否全为1""" n_one, n_all = count_one(x) return n_one == n_all def ones2int(n_bits): """获取具有 n_bits 个 1 的十进制数,eg. 1111 -> 15""" bi_str = "1"*n_bits return int(bi_str , 2) def voil_search(a, b): """暴力搜索""" most_lonely = a measure_lonely, _ = count_one(a) for x in range(a+1, b+1): meas, _ = count_one(x) if meas > measure_lonely: measure_lonely = meas most_lonely = x return most_lonely, measure_lonely def search(a, b): """各种情况汇总""" # 第一种情况: 相等 if a == b: return a # 第二种情况: b 全是1,当然他最多 if all_ones(b): return b # 第三种情况: 构造比b 低一位的全1二进制数 b1 n_one_b, n_all_b = count_one(b) b1 = ones2int(n_all_b - 1) # 如果 a <= b1, 那最多1就只能有这么多个 if a <= b1: return b1 # 最后,暴力搜索吧,这时候 a和b是一个数量级的 # 但是,暴力搜索复杂度不能满足要求 # 递归搜索:寻找 a = 101000 与 b = 101101 的光棍数 # 等价于 a = 1000 与 b = 1101 的光棍数 minus_val = 0 a_bi_str, b_bi_str = bin(a)[2:], bin(b)[2:] n_bits = len(a_bi_str) i = 0 while a_bi_str[i] == b_bi_str[i]: if a_bi_str[i] == "1": minus_val += int(2**(n_bits - 1 - i)) i += 1 most_lonely = search(a - minus_val, b - minus_val) return most_lonely + minus_val #=============================================================== if __name__ == "__main__": T = int(input()) for i in range(T): # 每行输入 num_str = input().strip().split(" ") a, b = int(num_str[0]), int(num_str[1]) most_lonely = search(a, b) print("Case {}: {}".format(i+1, most_lonely))