Very Computer

Hi,

Recently on the GMP (GNU multiple-precision library) mailing list, the issue
came up of how to test an integer to see if it is a power of 2 (such as 1,
2, 4, 8, 16, etc.). This is the solution that was finally decided on (in
'C'):

if ((x & (x-1) == 0) && (x != 0))

Not everybody necessarily speaks 'C', so let me explain that "&" is the
bitwise-AND operator and "&&" is the logical-AND operator.

I've included some examples of this test being applied at the end of the
e-mail. This should resolve any ambiguity.

Here is my question: What is the mathematical framework for this solution?
In other words, given a certain test to apply and a machine instruction set,
it is not clear to me how to choose the optimal series of instructions. Is
there an area of mathematics that covers this?

The solution that was supplied on the GMP list was very clever, but I don't
know of any way to generalize this.

For example, if I were to say I'd like to test if an integer is a power of
5, it is not clear how to choose the optimal series of instructions in a
rigorous framework (of course, powers of 2 are a bit of a special case given
the way computers are implemented).

All of the algorithms that come to mind are exponential, which makes them
unattractive.

Any assistance you could provide would be appreciated.

Best regards, Dave Ashley.

Examples are included below.

-----------------------------------------------

Voice: (313) 832-0118

FAX: (530) 688-6564

EXAMPLES BELOW.

EXAMPLE #1: IS 0 A POWER OF 2?

The second test (x != 0) fails, so it is not. Note that this test is
logically AND'd to form the result, so if this second test is false the test
overall is false.

EXAMPLE #2: IS 64 A POWER OF 2?

The bit pattern of 64 is 1000000.

The bit pattern of 64-1 = 63 is 01111111.

Bit-wise AND'ing these together gives 0000000.

So, the first test x & (x-1) == 0 is met. The second test is also met. So
the test overall is TRUE.

EXAMPLE #3: IS 9 A POWER OF 2?

The bit pattern of 9 is 1001.

The bit pattern of 9-1 = 8 is 1000.

Bit-wise AND'ing these together gives 1000.

Hence, the first test x & (x-1) == 0 fails and the test overall fails.

END OF EXAMPLES

As far as I understand what you're asking I would look to Knuth's TAOCP for
a mathmatical way to express this.

Quote:

> The solution that was supplied on the GMP list was very clever, but I
> don't know of any way to generalize this.
> For example, if I were to say I'd like to test if an integer is a power of
> 5, it is not clear how to choose the optimal series of instructions in a
> rigorous framework (of course, powers of 2 are a bit of a special case
> given the way computers are implemented).

> All of the algorithms that come to mind are exponential, which makes them
> unattractive.

The fastest, way I can think of to do this, which would also be Base
independant would be to create a huge array map. It's a ton of work at
coding time, but will reduce execution time.

int powermap[]={0,1,1,0,1,0,0,0,1 .... }; // for powers of two
int fivemap[]={0,1,0,1,0,0,0,0,0,1 ... }; //for powers of three

if (powermap[x]) { /* power of 2 */ };

in other words  powermap[0] = 0,
                powermap[4] = 1,
                powermap[11] = 0

Get the picture? only problem is the programmer has to build the huge
array, which will consequently take a huge amount of memory.

This only works for unsigned integers and binary representation,
and is quite straightforward.  You need nothing more than based
representation.  If you are willing to accept that 0 is a power of
2 you can eliminate the extra test.

To see that subtracting one leaves the high order bit unchanged
for non-power values, simply consider the propagation of 'borrows'
from the low order bit during the subtraction.  Any extra 1 bit
will satisfy the borrow, and prevent further propagation. This
leaves the high order bit unchanged, and at least one low order
bit set, so that the logical and leaves at least one bit set, and
a non-zero result.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

On Wed, 5 Jun 2002 00:06:43 -0400, "David T. Ashley"

Quote:> Hi,

> Recently on the GMP (GNU multiple-precision library) mailing list, the issue
> came up of how to test an integer to see if it is a power of 2 (such as 1,
> 2, 4, 8, 16, etc.). This is the solution that was finally decided on (in
> 'C'):

> if ((x & (x-1) == 0) && (x != 0))

The second test may be practical for the purpose that you want, but it
is not mathematically valid for testing since 0 is a power of 2 (2^0),
just as it is a power of every other number.

Quote:> Not everybody necessarily speaks 'C', so let me explain that "&" is the
> bitwise-AND operator and "&&" is the logical-AND operator.

> I've included some examples of this test being applied at the end of the
> e-mail. This should resolve any ambiguity.

> Here is my question: What is the mathematical framework for this solution?
> In other words, given a certain test to apply and a machine instruction set,
> it is not clear to me how to choose the optimal series of instructions. Is
> there an area of mathematics that covers this?

Once upon a time, a long, long time ago, I mused on the fact that 10 -
1 is equal to 9, 100 - 1 is divisible by 9, 1,000,000,000 is divisible
by 9 and so on.  Out of sheer utter boredom I spent a little time to
see how difficult it would be to work out a general proof that for any
value n > 0, 10^n - 1 is evenly divisible by 9.

That means that you can observe the pattern in decimal as well, and
you could observe the same results if there was such a thing as a
decimal digit by digit and operator, such that the result is 0 if
either or both decimal digits are 0, and the result is not 0 but
unspecified (not needed for this purpose) if neither digit is 0.

10000 - 1 = 00999.  10000 (digitAND) = 00000.

Two other things about the "power of 10 minus 1" scenario I worked on
(and yes, I am aware that this is trivial).

1.  Subtracting 1 from a power of 10 is just a special case of
subtracting a smaller positive power of ten from a larger positive
power of 10.  That is given m > 0, n > 0, m > n, 10^m - 10^n is evenly
divisible by 9.

2.  It was a long time ago, and I do not remember the proof, just the
result.

But you might consider starting there.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

Hi,

Last time I checked 0 was not a finite power of 2: 2^0 = 1

Regards,
Dave

No you're not mathmatically valid, (2^0)=1 just as 1 is the 0th root of any
number.

Quote:> Once upon a time, a long, long time ago, I mused on the fact that 10 -
> 1 is equal to 9, 100 - 1 is divisible by 9, 1,000,000,000 is divisible
> by 9 and so on.  Out of sheer utter boredom I spent a little time to
> see how difficult it would be to work out a general proof that for any
> value n > 0, 10^n - 1 is evenly divisible by 9.

Now if you're earlier statement had been correct that n^0=0, then this
would have to be for n>=0 since 0 is divisible by 9.