Powers of 2

Saturday, April 2, 2011

I came across a blog post discussing an interview question for developers:

“Write a function to determine if a number is a power of 2.”

Subsequently, I noticed a great discussion on StackOverflow discussing methods of solving this problem, and another blog post describing ten ways to do this in C. I’ve translated a few implementations into Factor to contrast the various approaches. The signature of the words we will create looks like this:

: power-of-2? ( n -- ? )

And some basic test cases used to verify that it works:

{ t } [ {  1 2 4 1024 } [ power-of-2? ] all? ] unit-test
{ f } [ { -1 0 3 1025 } [ power-of-2? ] any? ] unit-test

Implementations

We can shift the number to the right, checking to see that the first odd value observed is 1:

: shift-right/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ [ dup even? ] [ 2/ ] while 1 = ] if ;

Or, we can use a virtual sequence of bits and count the number of “on” bits (should be only 1):

: bits/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ make-bits [ t? ] count 1 = ] if ;

Or, we can compute the integer log2 raised to the second power, and compare:

: log2/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ dup log2 2^ = ] if ;

Or, we can calculate the next-power-of-2, and compare:

: next-power/power-of-2? ( n -- ? )
    dup 1 = [ drop t ] [ dup next-power-of-2 = ] if ;

Or, we can compare the number with its two’s complement:

: complement/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ dup dup neg bitand = ] if ;

Or, we can decrement the number and compare it with the original:

: decrement/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ dup 1 - bitand zero? ] if ;

Or, we can define a lookup table (using the literals vocabulary to define the table at compile time) holding all possible 64-bit powers of 2 (restricting the range of valid inputs to 64-bits):

CONSTANT: POWERS-OF-2 $[ 64 <iota> [ 2^ ] map ]

Using this, we can check a given number against all the values in the lookup table:

: check-all/power-of-2? ( n -- ? )
    POWERS-OF-2 member? ;

Or, we can do a linear search, stopping when we see numbers too large:

: linear-search/power-of-2? ( n -- ? )
    POWERS-OF-2 over [ >= ] curry find nip = ;

Or, knowing that the lookup table is sorted, we can do a binary search:

: binary-search/power-of-2? ( n -- ? )
    POWERS-OF-2 sorted-member? ;

Or, we can compute a hash-set (at compile time), and check for membership:

: hash-search/power-of-2? ( n -- ? )
    $[ POWERS-OF-2 fast-set ] in? ;

Or, we can use the integer log2 as an index into the lookup table.

: log-search/power-of-2? ( n -- ? )
    dup 0 <= [ drop f ] [ dup log2 POWERS-OF-2 nth = ] if ;

Testing

We can make a list of all our implementations:

CONSTANT: IMPLEMENTATIONS {
    shift-right/power-of-2?
    bits/power-of-2?
    log2/power-of-2?
    next-power/power-of-2?
    complement/power-of-2?
    decrement/power-of-2?
    check-all/power-of-2?
    linear-search/power-of-2?
    binary-search/power-of-2?
    hash-search/power-of-2?
    log-search/power-of-2?
}

And then test their functionality:

: test-power-of-2 ( -- ? )
    IMPLEMENTATIONS [
        1quotation [ call( n -- ? ) ] curry
        [ {  1 2 4 1024 } swap all? ]
        [ { -1 0 3 1025 } swap any? not ] bi and
    ] all? ;

Sure enough, they seem to work:

IN: scratchpad test-power-of-2 .
t

Performance

We can benchmark the performance of the various implementations operating on 1,000,000 random 32-bit numbers:

: bench-power-of-2 ( -- assoc )
    IMPLEMENTATIONS randomize 20 2^ [ random-32 ] replicate '[
        [ name>> "/" split1 drop ] [
            1quotation [ drop ] compose
            [ each ] curry [ _ ] prepose
            nano-count [ call( -- ) nano-count ] dip -
        ] bi
    ] { } map>assoc ;

Running the benchmark, we see that log2/power-of-2? is the (slightly) fastest version:

The raw numbers from one of my benchmark runs:

IN: scratchpad bench-power-of-2 sort-values .
{
    { "log2" 118107290 }
    { "complement" 119691428 }
    { "decrement" 121455742 }
    { "log-search" 122799186 }
    { "next-power" 127366447 }
    { "shift-right" 137695485 }
    { "binary-search" 204224141 }
    { "check-all" 267042396 }
    { "hash-search" 269629705 }
    { "linear-search" 280441186 }
    { "bits" 1112186059 }
}

Improvement

But, can we do better? We have already created a faster implementation than the math vocabulary, which defines power-of-2? using “decrement”. Focusing on that implementation, perhaps we can still introduce some improvements.

We can do less work, by exiting early using a short-circuit combinator if the first test fails:

: decrement+short/power-of-2? ( n -- ? )
    { [ dup 1 - bitand zero? ] [ 0 > ] } 1&& ;

Or, we can add type information, assuming only fixnum values (restricting our possible input values to a 60-bit number between -576,460,752,303,423,488 and 576,460,752,303,423,487):

TYPED: decrement+typed/power-of-2? ( n: fixnum -- ? )
    dup 0 <= [ drop f ] [ dup 1 - bitand zero? ] if ;

Or, if we are okay with restricting the input values, we can try writing it in C:

1. Build a simple C function in power-of-2.c:

#include <stdint.h>

int64_t isPowerOfTwo (int64_t x)
{
    return ((x > 0) && ((x & (x - 1)) == 0));
}

2. Build a C library we can use :

$ cc -fno-common -c power-of-2.c
$ cc -dynamiclib -install_name power-of-2.dylib \
     -o power-of-2.dylib power-of-2.o
$ sudo mv power-of-2.dylib /usr/local/lib

3. Wrap the C library from Factor (using the alien vocabulary):

USING: alien alien.c-types alien.syntax alien.libraries ;

"libpowerof2" "power-of-2.dylib" cdecl add-library

LIBRARY: libpowerof2

FUNCTION: int isPowerOfTwo ( int x )

4. And, finally, build a Factor word that uses it:

: decrement+alien/power-of-2? ( n -- ? )
    isPowerOfTwo 1 = ;

Running the benchmarks shows the typed version only slightly beating the short-circuit version, with a roughly 10% improvement:

{
    { "decrement+typed" 111711456 }
    { "decrement+short" 112070520 }
    { "decrement+alien" 113014058 }
    { "decrement" 123256748 }
}

Given that we want some ability to generalize our function to all integer inputs, I’d be happy declaring decrement+short/power-of-2? the “winner”. Can you do better?

The code for this is on my GitHub.