How Can We Efficiently Determine if a Number is a Power of 2?

Determine whether a number of numbers is 2

Problem description

Determine whether the given number is the power of 2, which requires a simple and accurate algorithm. The author proposes two algorithms, but encountered the problem when using the calculation of numbers.

The first algorithm

The first algorithm Use a simple cycle to check the power of 2 through the displacement:

This method is simple and easy to understand, and it can run perfectly for any IsPowerOfTwo value.

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

    for (ulong power = 1; power > 0; power = power << 1)
    {
        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

The second algorithm

ulong

The second algorithm Relying on the calculation of numbers:

However, due to the problem of discarding, this algorithm cannot be properly handled 9223372036854775809.

The improved algorithm IsPowerOfTwo_2

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

Algorithm explanation

This improved algorithm cleverly uses the bit operation:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

Bit operator Check whether the two bits of the corresponding position are 1.

Subtract 1 from the number to turn all 1 to 0, and turn all 0 to 1.

If the number is the power of 2, the binary indicates that there will be only one digit.

When the number and (x -1) are performed and the operation, all the bit except 1 on the far right will be 0.

• Therefore, if the result is 0, the number is the power of 2. &
• Remove zero
• In order to eliminate zero (zero -not -considered power is 2), additional conditions
.

The above is the detailed content of How Can We Efficiently Determine if a Number is a Power of 2?. For more information, please follow other related articles on the PHP Chinese website!