名企笔试:2017美团java工程师笔试编程题(特殊运算)

2017美团java工程师笔试编程题


1、题目要求

 

给定 x, k ,求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算,例如 3 | 5 = 7。

比如当 x=5,k=1时返回 2,因为5+1=6 不等于 5|1=5,而 5+2=7 等于 5 | 2 = 7。

现在要求 0 < x , k ≤ 2,000,000,000 ,假设x = 5,k = 1,输出的结果应该是2,2是第一个能满足 x + y = x | y 的y值

定义函数为

def func(base,index)
func(5,1) = 2
func(5,2) = 8


2、程序分析

 

  • 5的2进制表示是 1 0 1,2的2进制表示是 0 1 0 ,7 的2进制表示是 1 1 1
  • x和y的值满足 x + y = x | y ,那么在2进制上必然呈现这样的特点,相同位上,一个数的值如果为1,另一个数的值只能为0,一个数的值为0,则另一个数的值可以为0或者1,这样,相同位做相加操作和做或操作后,才会是相等的
  • 以5为例,二进制为101,前面还有许多0,因此,要补齐,补齐后是 0000000000000000000000000000101  ,剩下的事情,就是找到那些符合上面所说特点的数值
  • 以5为例,x = 5,对于y来说,y的2进制必须满足这样的要求,第1位必须为0,第2位可以为0或1,第3位是0,第4位是0或1,以此类推
  • 知道了二进制各个位上允许的值,就可以做排列组合,比如 0 1 0 就是3个二进制位可以满足要求的y,1010就是4个二进制位可以满足要求的y

3、示例代码

 

#coding=utf-8

# 两个list中的元素排列组合成一个新的list
def merge_lst(lst1,lst2):
    lst = []
    if lst2 == []:
        return lst1

    for i in lst1:
        for j in lst2:
            lst.append(i+j)

    return lst

def func(base,index):
    bin_str = bin(base)
    tail = bin_str[2:]
    tail = '0' * (31-len(tail)) + tail
    lst = []
    for i in range(len(tail)):
        tmp = []
        if tail[i] == '0':
            tmp.append('0')
            tmp.append('1')
        else:
            tmp.append('0')
        lst.append(tmp)

    g_lst = []
    number_lst = []
    #计算不同2进制长度的y的值
    for i in range(len(lst)-1,-1,-1):
        g_lst = merge_lst(lst[i],g_lst)
        print g_lst
        for item in g_lst:
            item = int(item,2)
            if item > 0 and not item in number_lst:
                number_lst.append(item)
            if len(number_lst) == index:
                return number_lst[-1]

print func(5,4)