如何检查一个数字是否是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。

有没有更好的算法?

当前回答

return ((x != 0) && !(x & (x - 1)));

如果x是2的幂，它唯一的1位在位置n。这意味着x - 1在位置n有一个0。要了解原因，请回忆一下二进制减法是如何工作的。当x减去1时，借位一直传播到位置n;位n变为0，所有低位变为1。现在，由于x和x - 1没有共同的1位，x & (x - 1)为0，并且!(x & (x - 1))为真。

2012-12-21 11:49:06

其他回答

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

2009-07-21 20:29:18

这是另一种方法

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

对于2的任意次幂，也成立。

n& (-n) = = n

注意:n=0失败，需要检查这样做的原因是: -n是n的2s补。-n将使n的最右集合位左边的每一位与n相比翻转。对于2的幂，只有一个集合位。

2016-05-29 17:45:11

求给定的数是否为2的幂。

#include <math.h>

int main(void)
{
    int n,logval,powval;
    printf("Enter a number to find whether it is s power of 2\n");
    scanf("%d",&n);
    logval=log(n)/log(2);
    powval=pow(2,logval);

    if(powval==n)
        printf("The number is a power of 2");
    else
        printf("The number is not a power of 2");

    getch();
    return 0;
}

2010-03-31 11:46:04

例子

0000 0001    Yes
0001 0001    No

算法

使用位掩码，将变量以二进制形式除以NUM IF R > 0 AND L > 0:返回FALSE 否则，NUM变为非零如果NUM = 1:返回TRUE 否则，请执行步骤1

复杂性

时间~ O(log(d))，其中d为二进制位数

2015-07-28 06:03:04

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

推荐文章

最新文章

标签