思科笔试题1

QQ叫紫珊

　　1. 用宏定义写出swap（x，y）
2.数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
3 一语句实现x是否为2的若干次幂的判断
4.unsigned int intvert(unsigned int x,int p,int n)实现对x的进行转换,p为起始转化位,n为需要转换的长度,假设起始点在右边.如x=0b0001 0001,p=4,n=3转换后x=0b0110 0001
　　参考答案：
　　1。
　　#define swap(x, y)/
x = x + y;/
y = x - y;/
x = x - y;

#define swap1(x, y)/
x ^= y;/
y ^= x;/
x ^= y;

对于swap，当输入的数据是不同种类型的话，这个宏的结果是不对的。
对于swap1，只适用于整型数据。
　　2。
　　第二题，采用hash表，对访问到的每一个数N，在hash表中记录其值为true,那么当再次访问到时，如果值已经为true，那么表明重复了，这样只要扫描一次，时间复杂度为O(n),而对hash表的访问时间复杂度是O(1)
3。
　　((i & (i - 1)) ? false : true)
　　4。
　　result ^= (  ((1<<n)-1)  <<  p );