一道淘宝笔试题之我见-欢迎大家指正

给定一个整数N，按照下列条件进行运算：若N为偶数将其除以2，若为奇数将其加1或者减1。

求一个算法按照上述运算方式使得其以最少的步骤变为1.

 

解题关键：将该整数N以二进制的形式表示出来，实际上就是进行逻辑右移和加减一的操作。要使得以最快速度变为1，就要求尽可能用移位操作而不是加减操作，也就是要使得加减操作所得到的二进制结果中产生尽可能少的1。如00100101减1以后变为00100100（还剩两个1），若进行加1为00100110（剩下三个1）这样就会需要更多的运算使之变为1. 当最后三位为101的时候进行减一操作无疑减少了1的出现，除了00000011进行减一操作外，诸如00000111、00001111、11111111都是加1操作。

按照上述思路得出下列Java代码：

while(true){
   if(n==1)//变为1 就退出
   {
       return;
   }else if((n&1)!=1){ //若为偶数
    n=n>>>1; //除以2(进行逻辑移位)
    System.out.println(n);
   }else{
    if((n&7)!=7) //判断最后三位是不是111，若是则加1，若不是自减1

    {                //(因为末尾三位为101或011都应该进行减1，若是111就加1)
       n--;
       System.out.println(n);
    }else
    {
       n++;
       System.out.println(n);
    }
   }
  }