Re: function to determine if an integer is divisible by 2
In article <JD9sLH.1z0F@beaver.cs.washington.edu>, See Website For
Email <SeeWebsiteForEmail@erdani.org> wrote:
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);
}
FWIW
It is also possible to do a binary search with templates, reducing the
recursion depth and only log2(digits) tests.
#include <limits>
// binary search [Min,Max).
template <int Min,int Max,int Width> struct power_two_table_entry
{
static const int Mid=(Min+Max)/2;
static bool exec(int n)
{
if(n==Mid) return true;
if(n< Mid)
return power_two_table_entry
<
Min,
Mid,
Width/2
>::exec(n);
return power_two_table_entry
<
Mid,
Max,
Width/2
>::exec(n);
}
};
template <int Min,int Max>
struct power_two_table_entry<Min,Max,1>
{
static bool exec(int n)
{ return n==Min;}
};
bool is_power_two(int n)
{
if(n < 1) return false;
return power_two_table_entry
<
1,
std::numeric_limits<int>::digits,
std::numeric_limits<int>::digits-1
>::exec(n);
}
No major trickery either...
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]