I'll answer this in increasing complexity and generality.
If x is fixed to 16 then just use a constant value
1118481
. Hooray! (Name it, using magical numbers is bad practice)If you have a few cases known at compile time use a few constants or even defines, for example:
#define X_2 63 #define X_4 1365 #define X_8 37449 #define X_16 1118481 ...
If you have several cases known at execution time initialize and use a lookup table indexed with the exponent.
int _X[MAX_EXPONENT]; // note: give it a more meaningful name :)
Initialize it and then just access with the known exponent of 2^exp at execution time.
newIndex = nowIndex + 1 + (localChildIndex*_X[exp]);
How are these values precalculated, or how to calculate them efficiently on the fly: The sum
X = x^n + x^(n - 1) + ... + x^1 + x^0
is a geometric serie and its finite sum is:X = x^n + x^(n - 1) + ... + x^1 + x^0 = (1-x^(n + 1))/(1-x)
About the bitwise operations, as Oli Charlesworth has stated if x is a power of 2 (in binary 0..010..0)
x^n
is also a power of 2, and the sum of different powers of two is equivalent to the OR operation. Thus we could make an expression like:Let
exp
be the exponent so that x = 2^exp. (For 16, exp = 4). Then,X = x^5 + ... + x^1 + x^0 X = (2^exp)^5 + ... + (2^exp)^1 + 1 X = 2^(exp*5) + ... + 2^(exp*1) + 1
now using bitwise,
2^n = 1<<n
X = 1<<(exp*5) | ... | 1<<exp | 1
In C:
int X; int exp = 4; //for x == 16 X = 1 << (exp*5) | 1 << (exp*4) | 1 << (exp*3) | 1 << (exp*2) | 1 << (exp*1) | 1;
And finally, I can't resist to say: if your expression were more complex and you had to evaluate an arbitrary polynomial
a_n*x^n + ... + a_1*x^1 + a_0
in x, instead of implementing the obvious loop, a faster way to evaluate the polynomial is using the Horner's rule.