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:

( 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:

( 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:

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

- 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

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

- 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.

## 2 comments:

Delightful. With SBCL:

(defun logcount-power-of-2-p (n)

(and (= 1 (logcount n))

(plusp n)))

(defun logand-power-of-2-p (n)

(and (zerop (logand n (1- n)))

(plusp n)))

SLIME> (time (loop for i from 1 to (expt 2 20) do

(logcount-power-of-2-p (random 1152921504606846975))))

Evaluation took:

0.073 seconds of real time

0.076661 seconds of total run time (0.076661 user, 0.000000 system)

105.48% CPU

175,873,707 processor cycles

0 bytes consed

NIL

SLIME> (time (loop for i from 1 to (expt 2 20) do

(bitand-power-of-2-p (random 1152921504606846975))))

Evaluation took:

0.070 seconds of real time

0.069996 seconds of total run time (0.069996 user, 0.000000 system)

100.00% CPU

166,922,226 processor cycles

0 bytes consed

NIL

Post a Comment