【C#实现漫画算法系列】-判断2的乘方

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

微信上关注了算法爱好者这个公众号，有一个漫画算法系列的文章生动形象，感觉特别好，给大家推荐一下（没收过广告费哦），原文链接：漫画算法系列。也看到了许多同学用不同的语言来实现算法，作为一枚C#资深爱好的小学生，我在这个系列就用C#来实现一下里面的算法。欢迎大佬来点评！

下面我来引述一下-判断 2 的乘方这个算法。

题目1：实现一个方法，判断一个正整数是否是2的乘方（比如16是2的4次方，返回True；18不是2的乘方，返回False）。要求性能尽可能高。

作为一枚工科生，我们首先想到的是从数学角度来解决这个问题，那么稍微想一下，就有思路了，数学解法的套路是：

解法1：设置一个中间变量temp，来存放2的n次方。方法中建立一个循环，在循环中将temp与该正整数x比较，若相等则说明x为2的乘方，否则temp数值乘2，在循环中继续与x比较。当temp大于x时，说明在小于x的2的乘方的数中没有与x相等的，x不为2的乘方，退出循环。实现代码为：

using System;

namespace powerof
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                int entry = int.Parse(Console.ReadLine());
                bool result = isPowerOfTwo(entry);
                Console.WriteLine("是否是2的乘方：{0}", result);
            }
            catch
            {
                Console.WriteLine("你输入的数字有误，请重新启动程序输入！");
            }
            Console.ReadKey();        
        }
        public static bool isPowerOfTwo(int number)
        {
            int temp = 1;
            while (temp <= number)
            {
                if (temp == number)
                {
                    return true;
                }
                temp = temp * 2;
            }
            return false;
        }
    }
}

这就是典型的用数学方法来解决问题的方式，这样做得到的结果绝对是正确的，但是效率并不高，需要多次在循环中让中间变量temp比较并乘2，算法的时间复杂度为O(logN)，空间复杂度为O(1)。

那么如何用程序员的思维、更加高效的解决这个问题呢？我们知道在C#中有一种运算叫做位运算，位运算的特点是：算术左移即操作数乘2，算数右移即操作数除2(快速记忆：左乘右除)，按位与0可将操作数按位清0，按位与1得到原操作数，按位或1可将操作数按位置1，按位异或0即得到原操作数，按位异或1即实现原操作数按位取反。还有等等一系列的用处就不一一列举了。

这里我们可以用位运算符来高效的解决有关二进制的问题。

解法2：实现方法大部分与上述方法一样，不同的是这里不需要让temp乘2，而是在循环中让temp左移一位实现乘2的效果。实现代码为：

        public static bool isPowerOfTwo(int number)
        {
            int temp = 1;
            while (temp <= number)
            {
                if (temp == number)
                {
                    return true;
                }
                temp = temp << 1;
            }
            return false;
        }

其实这里虽然用了位运算，但是解题的思路仍然和第一个解法是一样的，本质上讲只是换了一个运算temp的方式而已。时间复杂度和空间复杂度没有变。

那么到底怎样的思路才能最高效的解决这个问题呢？大家想一想，那些是2的乘方的正整数，例如1、2、4、8、16、18它们在二进制上都有什么样的特点呢？如下：

1： 00000001

2： 00000010

4： 00000100

8： 00001000

16： 00010000

18： 00010010

我们可以看到，它们的二进制数只有一位1。这条规律将会帮助我们实现一个时间复杂度为O(1)的算法，那么知道这个之后还要怎么办呢？其实由这条规律我们可以推出，当这些数减1之后：

1-1： 00000000

2-1： 00000001

4-1： 00000011

8-1： 00000111

16-1： 00001111

18-1： 00010001

即原数值最高位为0，低位全为1，这个时候我们让这个正整数和它减1后的结果按位相与，即x&x-1，得到的结果是：

1&1-1： 00000000

2&2-1： 00000000

4&4-1： 00000000

8& 8-1： 00000000

16&16-1： 00000000

18&18-1： 00010000

也就是说，在执行完上述操作后，若正整数为2的乘方，结果为0，否则结果非0。

解法3：当x&x-1后的结果为0时，该数为2的乘方。否则若结果不为0，该数不是2的乘方。我们用代码描述：

  public static bool isPowerOfTwo(int number)
        {

            return (number & number - 1) == 0;
        }

时间复杂度为O(1)，不需要额外空间。由于计算机中数的形式都为二进制，用二进制的方法来解决二进制问题往往比用十进制的数学方法要高效。

题目2 ：思考题实现一个方法，求出一个正整数转换成二进制后的数字“1”的个数。要求性能尽可能高。

同题目1一样，我们首先会想到数学方法解决这道题，Talk is cheap ,show you the code !

解法1：设置一个变量count存放正整数x的二进制中数字“1”的个数，将x对2取余数。若余数为1，则可得到x二进制的第一个位为1，count加1；若余数为0，x二进制第一个的个位为0，count不变。然后将x除2，相当于将二进制数右移一位。在循环中重复上述步骤，当x不大于0时结束循环。此时count值为x二进制中1的个数。

using System;

namespace powerof
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                int entry = int.Parse(Console.ReadLine());
                int result = counterOfOne(entry);
                Console.WriteLine("{0}转换成二进制后的数字“1”的个数为{1}", entry,result);
            }
            catch
            {
                Console.WriteLine("你输入的数字有误，请重新启动程序输入！");
            }
            Console.ReadKey();        
        }
         public static int counterOfOne(int number)
        {
            int count = 0;
            while (number > 0)
            {
                if(number%2==1)
                    count++;
                number = number / 2;
            }
            return count;
        }
    }
}

解法2：设置一个变量count存放正整数x的二进制中数字“1”的个数，判断x二进制最低位是否为“1”，若为1，count加1，否则count不变。将x向右移一位。在循环中重复上述步骤，当x不大于0时结束循环。此时count值为x二进制中1的个数。

using System;

namespace powerof
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                int entry = int.Parse(Console.ReadLine());
                int result = counterOfOne(entry);
                Console.WriteLine("{0}转换成二进制后的数字“1”的个数为{1}", entry,result);
            }
            catch
            {
                Console.WriteLine("你输入的数字有误，请重新启动程序输入！");
            }
            Console.ReadKey();        
        }
        public static int counterOfOne(int number)
        {
            int count = 0;
            while (number > 0)
            {
                if ((number&1)==1)
                    count++;
                number = number >> 1;

            }
            return count;
        }
    }
}

时间复杂度为O(logn)。

事实上这段代码的思想和上一个解法的思想是相同的，但是上一个解法用了数学方式解决，而这种解法用了位运算来解决。在这里，同样只有一个判断条件，就是循环条件。在循环中，count不停的加上x同1按位与的值，即加上x二进制最低位的值。最低位是1就加1，不是1就加0，相当于不变。然后，将x右移一位。在计算机中，运算速度：移位>乘法>除法。因此这段代码的运行时间要比上一个解法还要短。

解法3：

看起来似乎已经是最快的解法了，没错，但这仅仅是这个解题思路中的最快解法。我们总结一下，我们从开始看这个问题的开始，就一直用这一种思路：建立循环来将二进制移位，每次循环对当前最低位是否为1进行判断并计数，每次循环移一位。那么如果我们每次循环不止移一位呢？我们看上面描述的所有算法，无论二进制数中有几个1，都要一位一位的来判断。我们只有一次就跳到存有1的位置，才可以让算法的效率有质的飞跃。

可是我们每次移多位的话就会漏掉某一位，这样得到的结果是不正确的。怎么办？还记得我们的第一个题目吗？判断一个数是否为2的乘方，将其二进制x和x-1按位与。如果是2的乘方，结果为0，那么如果不是呢？举个例子：

18：00010010

18-1： 00010001

18&18-1： 00010000=16（十进制）

与运算后的结果为16，那么：

16： 00010000

16-1： 00001111

16&16-1： 00000000

与运算后的结果为0，我们这时候可以发现，18的二进制数中有2个1，进行了两次x&x-1的与运算后为0。

也就是说，每执行一次x&x-1，实际上消除了一个二进制数中从最低位开始数的第一个的1。这样的话，我们就可以将算法改为：

using System;

namespace powerof
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                int entry = int.Parse(Console.ReadLine());
                int result = counterOfOne(entry);
                Console.WriteLine("{0}转换成二进制后的数字“1”的个数为{1}", entry,result);
            }
            catch
            {
                Console.WriteLine("你输入的数字有误，请重新启动程序输入！");
            }
            Console.ReadKey();        
        }
        public static int counterOfOne(int number)
        {
            int count = 0;
            while (number > 0)
            {
                count++;
                //number=number & number - 1;
                number &= number - 1;
            }
            return count;
        }
    }
}

由于我们规定输入的是正整数，所以一开始就可以++count（如果输入的是0或负数，那么结果就不正确了，小心这个bug，看清题目要求）。执行x&x-1，将结果放入x。循环条件判断逗号后边的表达式，也就是x的值是否为0，若不是0继续循环，否则停止。

这种算法不需要二进制数一位一位的挪，可以一步就将低位开始的第一个1找到，时间复杂度大部分情况下远小于O(logN)。只有当二进制数为全1时，时间复杂度为O(logN)。

那么再说一个二进制中老生常谈的问题吧。

题目3：输出一个正整数的二进制数。

其实C#里面有一个方法直接转化，详见点击这个博客

但是我用另一个方法来实现：

using System;

namespace powerof
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                string entry = Console.ReadLine();
                string result = DecToBin(entry);
                Console.WriteLine("{0}转换成二进制后的数字为{1}", entry,result);
            }
            catch
            {
                Console.WriteLine("你输入的数字有误，请重新启动程序输入！");
            }
            Console.ReadKey();        
        }
       
            public static string DecToBin(string x)
          {
                             string z = null;
                             int X = Convert.ToInt32(x);
                             int i = 0;
                             double  a, b = 0;
                             while (X > 0)
                                 {
                                     a = X % 2;
                                     X = X / 2;
                                     b = b + a * Math.Pow(10, i);
                                     i++;
                                }
                             z = Convert.ToString(b);
                          return z;
                       }
      
    }
}