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