Asked  7 Months ago    Answers:  5   Viewed   54 times

Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

  1. Simple
  2. Correct for any ulong value.

I came up with this simple algorithm:

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;
}

But then I thought, how about checking if log2 x is an exactly round number? But when I checked for 2^63+1, Math.Log returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in doubles and not in exact numbers:

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

This returned true for the given wrong value: 9223372036854775809.

Is there a better algorithm?

 Answers

72

There's a simple trick for this problem:

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

Note, this function will report true for 0, which is not a power of 2. If you want to exclude that, here's how:

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

Explanation

First and foremost the bitwise binary & operator from MSDN definition:

Binary & operators are predefined for the integral types and bool. For integral types, & computes the logical bitwise AND of its operands. For bool operands, & computes the logical AND of its operands; that is, the result is true if and only if both its operands are true.

Now let's take a look at how this all plays out:

The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:

bool b = IsPowerOfTwo(4)

Now we replace each occurrence of x with 4:

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

Well we already know that 4 != 0 evals to true, so far so good. But what about:

((4 & (4-1)) == 0)

This translates to this of course:

((4 & 3) == 0)

But what exactly is 4&3?

The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers). So we have:

100 = 4
011 = 3

Imagine these values being stacked up much like elementary addition. The & operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);
return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

Tuesday, June 1, 2021
 
SkyNet
answered 7 Months ago
82

This problem is known as the subset sum problem, which is a special case of the Knapsack problem. Wikipedia is a good starting point for some algorithms.

Sunday, June 20, 2021
 
coolguy
answered 6 Months ago
86

Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms

Friday, July 23, 2021
 
DCD
answered 5 Months ago
DCD
29

If you are using Bash, you are better off using the arithmetic expression, ((...)) for readability and flexibility:

if ((number >= 2 && number <= 5)); then
  # your code
fi

To read in a loop until a valid number is entered:

#!/bin/bash

while :; do
  read -p "Enter a number between 2 and 5: " number
  [[ $number =~ ^[0-9]+$ ]] || { echo "Enter a valid number"; continue; }
  if ((number >= 2 && number <= 5)); then
    echo "valid number"
    break
  else
    echo "number out of range, try again"
  fi
done

((number >= 2 && number <= 5)) can also be written as ((2 <= number <= 5)).


See also:

  • Test whether string is a valid integer
  • How to use double or single brackets, parentheses, curly braces
Friday, July 30, 2021
 
Shamoon
answered 4 Months ago
18

The docs suggest a similar method, so I doubt you'll get any better. Remember to include an epsilon to take into account precision issues!

is.naturalnumber <-
    function(x, tol = .Machine$double.eps^0.5)  x > tol & abs(x - round(x)) < tol
is.naturalnumber(1) # is TRUE
(x <- seq(1,5, by=0.5) )
is.naturalnumber( x ) #-->  TRUE FALSE TRUE ...
Friday, August 6, 2021
 
Dennis
answered 4 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share