程序员面试金典day12

位运算好烦啊

Q1:编写一个函数，确定需要改变几个位，才能将整数A转变成整数B。 给定两个整数int A，int B。请返回需要改变的数位个数。

思路

异或求1

Code

python

# -*- coding:utf-8 -*- class Transform: def calcCost(self, A, B): # write code here Re=A^B count=0 while (Re!=0): Re=Re&(Re-1) count+=1 return count

Q2:请编写程序交换一个数的二进制的奇数位和偶数位。（使用越少的指令越好） 给定一个int x，请返回交换后的数int。

思路

单独求出奇数位与偶数位

Code

python

# -*- coding:utf-8 -*- class Exchange: def exchangeOddEven(self, x): # write code here x1=x&0xAAAAAAAA x2=x&0x55555555 return (x1>>1)+(x2<<1)

Q3:数组A包含了0到n的所有整数，但其中缺失了一个。对于这个问题，我们设定限制，使得一次操作无法取得数组number里某个整数的完整内容。唯一的可用操作是询问数组中第i个元素的二进制的第j位(最低位为第0位)，该操作的时间复杂度为常数，请设计算法，在O(n)的时间内找到这个数。 给定一个数组number，即所有剩下的数按从小到大排列的二进制各位的值，如A[0][1]表示剩下的第二个数二进制从低到高的第二位。同时给定一个int n，意义如题。请返回缺失的数。

思路

求最低位是否匹配就像

Code

python

class Finder: def findMissing(self, numbers, n): # write code here flag=1 for i in range(len(numbers)): tmp=numbers[i][0] if tmp!=flag: flag=tmp else: # return i tmps=[str(j) for j in numbers[i]] return eval("0b"+"".join(tmps[::-1]))-1 return n