《剑指offer》系列---2
1.求斐波那契数列的第N项
这个题目很简单，讲递归的书上都是用这个来讲的，但是面试的时候，如果你写个递归，那估计会让人失望的，因为递归的效率真是一个问题，你可以测试一下，输入50,基本上得到结果的时间，够你去喝杯茶了
/*int number_of1_in_binary(int m){ int count = 0; while(m) { if(m&1) count++; m>>=1; } return count;}*/但是这样有一个缺点，如果输入的数是负数怎么办呢？右移一位，左边的最高位补上的是1,到最后变成了0ＸＦＦＦＦＦＦＦＦ，陷入了死循环第二种：我们可以把移动1,每次比较之后，左移1一位，然后做与运算，就是下面的这样
/*int number_of1_in_binary(int m){ int count = 0, flag = 1; while(flag)//每次都把flag往左移动移位，移动32次 { if(m&flag) count++; flag = flag<<1; } return count;}*/但是这样我们就移动了32次，是不是有点多？，还有没有其它方法？第三种方法：考察一个数7,二进制111,7-1 = 6的二进制是110, 然后&7 = 110是6, 6-1 = 5的二进制是101,然后&6 = 100是4, 4-1 = 3的二进制是011,然后&4 = 0,我们发现每次把这个数-1然后与上这个数，得到数是原来这个数的最后右边的1变为0的值，由此我们得到如下的解法：
int number_of1_in_binary(int m){ int count = 0; while(m) { ++count; m = (m-1)&m; } return count;}如果你大笔一挥，一分种内写下如下的代码：那你就是和我一样的人，别人offer跳板的人
SLnode getKnode(SLnode head, int k){ if(head == NULL || head->next == NULL || k == 0) return NULL; SLnode node1 = head; SLnode node2 = head->next; while(k >= 1 && node1 != NULL) { node1 = node1->next; k--; } if(node1 == NULL) return NULL; while(node1->next != NULL) { node1 = node1->next; node2 = node2->next; } return node2;}