Determining whether a number is a power of four in time O(log log n)

Question

For an assignment, I need to find an algorithm that can test if a number n is a power of four in time O(log log n) time. I have no idea how to approach this and don't know what data structures or algorithms would be appropriate. Does anyone have any suggestions about how to approach this problem?

Answer 1

You can do better than O(log log N) if you know the word size--in fact, you can do it in O(1) with what should compile down to 4 machine instructions. For example, if you assume 32-bit ints, you can do this:

int is_power_of_4(int x) {
    return ( (x & (-x)) & 0x55555554 ) == x;
}

For different word sizes, just change the constant.

The x & (-x) trick is a well known hack that returns a number that is only the least significant 1 bit in x. The & 0x5554 then masks off the odd powers of two, then comparing to the original fails if there were any other set bits in x.

Answer 2

The O(log log n) requirement is a little odd. If you're dealing with unbounded integers, and those integers are represented in the usual binary form, then you can't really escape the need to examine all the bits of n. In that case, you're not going to be able to do better than O(log n). On the other hand, if you're just counting basic operations, it can be done in O(1) time.

Here's some Python code:

>>> def is_power_of_four(n):
...     return n & (n-1) == 0 and n % 3 == 1
... 
>>> [n for n in range(-10**6, 10**6) if is_power_of_four(n)]
[1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144]

In terms of bit operations, this algorithm is O(log n). In terms of operation counts, it's O(1). Explanation: n & (n-1) is the bitwise and operation applied to n and n-1. That's zero if and only if either n is a power of two or n == 0. And of the powers of two, the powers of four all have remainder 1 modulo 3, while the other powers of two have remainder 2. The remainder test also conveniently excludes the case n == 0.

If you also want to know which power of four n is, rather than just determing whether n is a power of four or not, then that's a different question, and templatetypedef already gives an efficient answer.

Answer 3

I'm going to assume that numbers are represented as fixed-width integers, which allows basic operations like comparisons, additions, multiplications, etc. to be done in time O(1).

Note that if you have a number n, that number n has O(log n) bits in it. If we let b be the number of bits in the number, then the desired runtime would be O(log b). In other words, we want to find some function whose runtime is logarithmic in the number of bits in the number.

Since we're trying to check if the number is a power of four, we're trying to see if the number has the form 4^k for some number k. Here's one possible approach we could use to do this:

1. Compute 4¹, 4², 4⁴, 4⁸, 4¹⁶, ..., 4^2x until we find a number that's bigger than the number n. This means that if n is a power of four, then it has to be a power of four sandwiched between 4⁰ and 4^2x. This step will end up taking O(log log n) time for the following reason: The number n can be written as 4^{log₄ n}. The above process terminates as soon as 4^2x ≥ 4^log₄n, which happens as soon as 2^x ≥ log₄ n, which happens when x ≥ log₂ log₄ n. There are therefore only O(log log n) total iterations, and each iteration takes time O(1).

2. Do a binary search over the range [0, 2^x] to determine what value of k, if any, satisfies n = 4^k. The runtime of this step will be O(x) because in a range of size 2^x a binary search will take time O(log 2^x) = O(x). Moreover, we know that x = O(log n). In step (1), we kept doubling the exponent until it overshot the value of log₄ n. This means that in the worst case, x can be 2 log₄ x, and so x = O(log n). Therefore, this step takes O(log log n) time as well.

Since steps (1) and (2) each take time O(log log n), the overall time complexity is O(log log n).

A note: You can think of this problem as a variant of the "guess the number game" on the logarithm of n. A classic interview question is "I'm thinking of a natural number n and you should try to guess it." You can solve it in O(log n) time by using pretty much the above approach. In this case, you're trying to guess the exponent of 4 that works, so you can apply the procedure to the logarithm of the number to get a runtime of O(log log n).

Hope this helps!

Answer 4

For unsigned integers you can use this:

bool is_pow4(DWORD x)
    {
/*
    4^0 =    1 = 00000000001b
    4^1 =    4 = 00000000100b
    4^2 =   16 = 00000010000b
    4^3 =   64 = 00001000000b
    4^4 =  256 = 00100000000b
    4^5 = 1024 = 10000000000b
    -------------------------
    or together  10101010101b
    negate       01010101010b = A....AAAh

*/
    if (!x) return false;
    if (DWORD(x&(x-1))) return false;   // not power of 2 (more than 1 bit is set)
    return !(x&0xAAAAAAAA);             // not setted any bit from negated mask
    }

• its basically similar to Lee Daniel Crocker answer
• but it use just unsigned ints
• and also detects 1 as power of 4 which is true (Lee Daniel Crocker code is wrong for that)
• also added some rems to better understand how it works
• the main idea is pow2 detection
• pow2 number is just 1 set bit and zeros (binary)
• so pow2 -1 is just ones (binary)
• if you and it together should get 0 as result
• to assume if it is also power of 4 just use negated mask
• if bit is set on the wrong place (pow2 not pow4) than simple and detect it
• can use any bit-count ... mask is allways AAAAAAA....AAAAAh for powers of 4

Also very similar problem is solving here: https://stackoverflow.com/a/19888301/2521214

PS. complexity is the same as x--,&

• so for normal numbers O(1)
• and for bignums depends on implementation usually O(log n)
• log by the base of bignum for example log(2^32,n)

Answer 5

Slightly more portable regarding the usage of mask.

#include <stdio.h> 
#include <string.h>

int main ()
{
   int x;
   int mask;

   memset(&mask, 0x55, sizeof(int));
   scanf("%d",&x);

   if ((x) && ((x & (x-1)) == 0) && (x & mask))
       printf("Power of four\n");
   else
       printf("Not power of four\n");
   return (0);
}

Answer 6

Provide a machine portable solution here. this solution doesn't require any precalculated number and doesn't make any assumption about the bit width of the machine.

bool isPowerOfFour(int num) {
    int s = ceil(sqrt(num));
    // s > 0 makes sure 0 is not power of four
    // 4^x -> 2^(2x) so sqrt of it should be 2^x all we need to do is to tell whether the sqrt is a power or two
    // but firstly we need to make sure sqrt(num) is an integer so we use s*s == num
    // then use (s&(s-1)) == 0 to tell whether it is a power of 2
    return s > 0 && s*s == num && (s&(s-1)) == 0; 
}