欢迎关注大数据技术架构与案例微信公众号:过往记忆大数据
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
过往记忆大数据

如何快速判断正整数是2的N次幂

  这个问题可能很多面试的人都遇到过,很多人可能想利用循环来判断,代码可能如下所示:

    public static boolean isPowOfTwo(int n) {
        int temp = 0;
        for (int i = 1; ; i++) {
            temp = (int) Math.pow(2, i);
            if (temp >= n)
                break;
        }
        if (temp == n) return true;
        else return false;
    }

  上面的代码简单明了。但是,这样的方案效率比较低。我们仔细分析一下,正整数是2的n次幂他有什么规律?20=1,21=2,22=4,23=8....这样看是没有什么规律的。但是如果将2的幂次方写成二进制形式后,很容易就会发现有以下两个特点:
  1、20=1 -> 0001,21=2 -> 0010,22=4 ->  0100,23=8  -> 1000二进制中只有一个1,并且1后面跟了n个0。
  2、如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1;因此将原来的数与去减去1后的数字进行与运算后会发现为零((x & x- 1) == 0)。
  原因:因为2n换算是二进制为10……0这样的形式,2n-1的二进制为0111...1,两个二进制求与结果为0,例如:16的二进制为10000;15=01111,两者相与的结果为0。计算如下:

  10000
&01111
  -------
  00000

所以可以用下面算法实现

  public static boolean isPowerOfTwo(int x) {
    return x > 0 & (x & (x - 1)) == 0;
  }

  很简单的一行代码就实现了。细心的读者可能会问:2的n次幂二进制始终都是只有一个1,其它的位数都为0,是否可以判断给定的数转换为二进制来判断其中是否只有1个1来得出给定数是否为2的n次幂呢?答案是不能。因为Integer.MIN_VALUE的二进制只有1个1,但是Integer.MIN_VALUE并不是2的n次幂,所以不能用上面方式来实现。(完)

本博客文章除特别声明,全部都是原创!
原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【如何快速判断正整数是2的N次幂】(https://www.iteblog.com/archives/716.html)
喜欢 (14)
分享 (0)
发表我的评论
取消评论

表情
本博客评论系统带有自动识别垃圾评论功能,请写一些有意义的评论,谢谢!
(6)个小伙伴在吐槽
  1. 楼主,为了讨论,我特意注册了下。
    你这个算法也没判断负数,如果是负数,先取负。如果是MIN_VALUE,特殊处理,直接是2的幂啊,因为MIN_VALUE=-2的31次幂

    对不对?

    twtsse032015-03-26 18:03 回复
    • 我这里只能判断出正数是否为2的幂,负数都不是,因为我这里只考虑了(2)^N,不是(-2)^N,也不是-2^N。我不知道你所说的是哪种情况?能不能说下?

      w3970907702015-03-26 19:04 回复
      • 不好意思,我整混淆了,我把你的问题理解成了类似 2^N 和(-1)*(2)^N -- 你回复里提到的-2^N :)

        twtsse032015-03-27 14:02 回复
        • 如果是(-1)*(2)^N,只需要将它变成正数,如果是MIN_VALUE需要特殊处理。
          如果是(-2)^N,稍微麻烦一些。

          w3970907702015-03-27 14:27 回复
          • 嗯,谢谢。从你这学到不少

            twtsse032015-03-27 15:06
  2. 非常犀利的算法,受教了!!!

    panda2013-12-24 06:43 回复