算术模块

1. 函数a定义如下:

• 调用函数a(666)返回的结果是: 1023

  int a(int tab){
   int n=tab-1;
   n |= n >> 1;
   n |= n >> 2;
   n |= n >> 4;
   n |= n >> 8;
   n |= n >> 16;
   return n;
  } 

• 解析：
  665的二进制数为：1010001111
  512 256 128 64 32 16 8 4 2 1
  1 0 1 0 0 0 1 1 1 1
  或运算 | ：只有同0才为0
  拿 n | (n>>1) 做例子，n>>1位变成了 0101000111，与1010001111 相或得到1111001111
  当 n | (n>>2) 时，结果就已经变成了 1111111111，所以为1023

• 在HashMap的源码，其中找到大于等于当前值的2的n次幂就是用的这个方法。

2. 已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 2

• 解析
  平均查找长度=总的查找次数/元素数
  总的查找次数： 38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
  25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
  74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
  63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
  52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
  48%7=6 （第1次出现6，有冲突，发现冲突6,0，故只能放到1，查找次数为3）
  1+1+2+1+4+3=12
  元素数=6
  所以：平均查找长度=12/6=2

3. 给定一个整型数组L，数组长度为n，数组元素取值范围[1,n],（n>2000)，请问最快速找出一个缺失值的时间复杂度是多少？ O(n)

• 解析
  数组并非排序