2^n, 2^n+1

I have a table generator routine that can only accept 2^n or 2^n+1 values.

Does anyone know if there is an easy way to check that an interger meets
that criteria other than enumerating thru the entire range of n?

There are probably cuteish methods, useful for very large n, but it isn't
expensive to loop 32 times or thereabouts--make a table of 2**n values if you
don't like the multiply. Then you can spend your time on the real problem.

Cheers,

Phil Hobbs

Thanks for the advice. The problem isn't really in the math. It's in the
programming language. In .NET I'll have to convert the a byte array and do a
bitwise comparison. A little harder than C or C++. Not really a big deal but
it's a real time app and if I can save a couple of clock cycles I will.

Kooter> Thanks for the advice. The problem isn't really in the math. It's in the
Kooter> programming language. In .NET I'll have to convert the a byte array and do a
Kooter> bitwise comparison. A little harder than C or C++. Not really a big deal but
Kooter> it's a real time app and if I can save a couple of clock cycles I will.

I didn't quite understand the question. You want to know if some
function is given 2^n or (2^n)+1 values? It's fairly easy to figure
out if x is of the form 2^n. x & (x-1) zaps the least significant bit
of x. If the result is 0, then x was of the form 2^n.

But maybe that's not what you want.

Ray

input is x, assumed to be >=1.
y = x shifted right by 1
z = y-1
w = logical and of y and z
then x = 2^n or 2^n+1 <=> w = 0.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode test 33Switch to Hybrid Mode Switch to Threaded Mode

1 13th April 00:01 kooter External User Posts: 1	2^n, 2^n+1 I have a table generator routine that can only accept 2^n or 2^n+1 values. Does anyone know if there is an easy way to check that an interger meets that criteria other than enumerating thru the entire range of n?

2 13th April 00:01 phil hobbs External User Posts: 1	2^n, 2^n+1 There are probably cuteish methods, useful for very large n, but it isn't expensive to loop 32 times or thereabouts--make a table of 2**n values if you don't like the multiply. Then you can spend your time on the real problem. Cheers, Phil Hobbs

3 13th April 00:01 kooter External User Posts: 1	2^n, 2^n+1 Thanks for the advice. The problem isn't really in the math. It's in the programming language. In .NET I'll have to convert the a byte array and do a bitwise comparison. A little harder than C or C++. Not really a big deal but it's a real time app and if I can save a couple of clock cycles I will.

5 13th April 00:28 george russell External User Posts: 1	2^n, 2^n+1 input is x, assumed to be >=1. y = x shifted right by 1 z = y-1 w = logical and of y and z then x = 2^n or 2^n+1 <=> w = 0.