如何检查一个数字是否是2的幂

今天我需要一个简单的算法来检查一个数字是否是2的幂。

该算法需要:

简单的适用于任何ulong值。

我想出了这个简单的算法:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

但后来我想:如何检查log2x是否恰好是一个整数呢?当我检查2^63+1时，Math.Log()因为四舍五入而返回恰好63。我检查了2的63次方是否等于原来的数，结果是正确的，因为计算是双倍的，而不是精确的数字。

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

这对于给定的错误值返回true: 9223372036854775809。

有没有更好的算法?

当前回答

这是另一种方法

package javacore;

import java.util.Scanner;

public class Main_exercise5 {
    public static void main(String[] args) {
        // Local Declaration
        boolean ispoweroftwo = false;
        int n;
        Scanner input = new Scanner (System.in);
        System.out.println("Enter a number");
        n = input.nextInt();
        ispoweroftwo = checkNumber(n);
        System.out.println(ispoweroftwo);
    }
    
    public static boolean checkNumber(int n) {
        // Function declaration
        boolean ispoweroftwo= false;
        // if not divisible by 2, means isnotpoweroftwo
        if(n%2!=0){
            ispoweroftwo=false;
            return ispoweroftwo;
        }
        else {
            for(int power=1; power>0; power=power<<1) {
                if (power==n) {
                    return true;
                }
                else if (power>n) {
                    return false;
                }
            }
        }
        return ispoweroftwo;
    }
}

2020-07-09 01:37:50

其他回答

一些网站记录并解释了这一点和其他一些无聊的黑客:

http://graphics.stanford.edu/~seander/bithacks.html (http://graphics.stanford.edu/ ~ seander / bithacks.html # DetermineIfPowerOf2) http://bits.stephan-brumme.com/ (http://bits.stephan-brumme.com/isPowerOfTwo.html)

他们的祖父，小亨利·沃伦(Henry Warren, Jr.)写的《黑客的喜悦》(Hacker’s Delight):

http://www.hackersdelight.org/

正如Sean Anderson的页面解释的那样，表达式((x & (x - 1)) == 0)错误地表明0是2的幂。他建议使用:

(!(x & (x - 1)) && x)

为了纠正这个问题。

2009-03-01 20:52:33

在发布了这个问题之后，我想到了以下解决方案:

我们需要检查是否有一个二进制数字是1。因此，我们只需将数字每次右移一位，如果它等于1则返回true。如果在任何时候我们得到一个奇数((number & 1) == 1)，我们知道结果是假的。这被证明(使用基准测试)对于(大)真值比原始方法略快，对于假值或小值则快得多。

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

当然，格雷格的解决方案要好得多。

2009-03-01 19:06:50

我看到很多答案都建议返回n && !(n & (n - 1))，但根据我的经验，如果输入值为负，它会返回假值。我将在这里分享另一种简单的方法，因为我们知道2的幂数只有一个集位，所以简单地，我们将计算集位的数量，这将花费O(log N)时间。

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

检查这篇文章数不清。固定位的

2020-06-09 14:51:59

下面是一个简单的c++解决方案:

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

2010-08-25 19:53:03

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

2010-09-03 18:36:51

如何检查一个数字是否是2的幂

推荐文章

最新文章

标签