Re: function to determine if an integer is divisible by 2
Carl Barron wrote:
In article <1171102541.055615.311310@v45g2000cwv.googlegroups.com>,
James Kanze <james.kanze@gmail.com> wrote:
I think it's an interesting exercise. It's pretty
straightforward if you use dynamic initialization for the
table, but then, you've written the algorithm twice. What
I'd like to see is some sort of meta-programming trick to
generate a staticly initialized C-style table.
I assume your table is not INT_MAX in size:) then it requires a look
up. Since numeric_limits<int>::digits is probably <= 128 a linear
search is all we need. If your compiler can fathom 128 levels of
template recursion then here is one table lookup solution.
#include <limits>
template <int N> struct power_two_table_entry
{
static bool exec(int n)
{
return n == N ? true:
power_two_table_entry<N/2>::exec(n);
}
};
template <> struct power_two_table_entry<0>
{
static bool exec(int) {return false;}
};
bool is_power2(int x)
{
return x < 1 ?
false :
power_two_table_entry<std::numeric_limits<int>::digits-1>::exec(x);
}
not much 'trickery':) I still prefer
inline bool is_power_two(int x) {return x>0 && x & (x-1) == 0;}
I still prefer the same; for solving the general problem I'd use code
much like yours, except that it starts from the lower ranks (because of
the "most numbers are small" mantra; not sure if that was ever shown or
not).
template <int base, int candidate, bool> struct power_table_entry
{
static bool exec(int n)
{
return n == candidate ? true:
power_table_entry<base, candidate * base,
(candidate <= INT_MAX / base)>::exec(n);
}
};
// hope I got the condition right...
template <int b, int c> struct power_table_entry<b, c, false>
{
static bool exec(int) {return false;}
};
template <int base>
bool is_power(int x)
{
return x < 1 ? false : power_table_entry<base, 1, true>::exec(x);
}
It's interesting to compare the solution with D, which makes it easy due
to static if (an "if" that guarantees non-compilation of the false branch):
bool is_power(int base, int candidate : 1)(int x)
{
static if (candidate > INT_MAX / base)
{
return false;
}
else
{
return x == candidate ? true :
is_power!(base, base * candidate)(x);
}
}
Andrei
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]