百度一道笔试题的解答

实现一个函数，对一个正整数n,算得到1需要的最少操作次数：

如果n为偶数，将其处以2；

如果n为奇数，可以加1或减1；

一直处理下去。

例子：

ret = func(7);

ret = 4,可以证明最少需要4次运算

n = 7

n-- 6

n/2 3

n-- 2

n/2 1

要求：实现函数（实现尽可能高效）

Int func(unsign int n)；n为输入，返回最小的运算次数。

给出思路（文字描述），完成代码，并分析你算法的时间复杂度。

请列举测试方法和思路

解答简单思路：
将n写成二进制，发现，对于连续的1少于2个时，直接用“减1法”，步骤最少；对于连续的1多于3个时，用“加1法”，再向右移位，步骤最少；对于连续的1刚好等于3时，减1或加1的步骤相同。

假定最后的处理结果是0（不是题意的1），那么：

1）每处理一个0，用移位，共需1步

2）处理连续d(d>=3)个1的，对其加1，再移动d位，共需1+d步

3）处理连续d(0
4) 由于题目要求处理到剩下最后一个1时停止，所以对于最高位的一连串1，需对结果作一定修正。

int func(unsigned int n){
int d, ret = 0;
while(n){
//连续0
while(!(n & 0x01)) n>>=1, ret++;
//连续1
for (d = 0; n & 0x01 << d; d++);
if (d < 3){
n >>= d;
ret += d << 1;
if (n == 0) ret --;
}else{
n++;
n >>= d;
ret += 1 + d;
}
}
ret--;
return ret;
}