思科笔试

原文地址：http://blog.sina.com.cn/s/blog_4cd4942f0100c67l.html

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.

Ros:
1, 确实可以有两种方法

#define SWAP(x,y) x+=y; y=x-y; x=x-y

#define SWAP(x,y) x^=y; y^=x; x^=y

第一中较通用，同类型都可以。第二种，以为采用位操作符，而float, double型的位操作是不能通过编译器的。但我始终觉得，不管是用什么数据类型，在内存中最终是二进制，这样第二种中逻辑上应该是能行的通的，只是不能通过编译。

2,
int do_dup(int a[], int N){
char *p_count,i;
p_count = (*char)malloc(N);//时间复杂度是o(N)但占用的空间多了点
for(i=0;i<N;i++){
    *(p_count+a[i])++;
    if(*(p_count+a[i]) == 2){
    return a[i];
    }
}

free(p_count);
}
当然，有人用hash表做的，可惜我没hash过。不过思路也没什么差异

3,Key: 2的n次幂在二进制上有共性，都是只有一个bit为1，其余全为0；
  (x&(x-1))?0:1 //1 for true, 0 for false

4,转换，其实就是每位都与1做异或的结果

unsigned int intvert(unsigned int x,int p,int n){

return x^=(((1<

}

一直没用过hash表，不过时常听说，好像数据库的基本结构都是这个东西，要想转到Storage，得花点时间弄明白。