Re: function to determine if an integer is divisible by 2
Gennaro Prota wrote:
On Sat, 10 Feb 2007 05:05:44 CST, James Kanze wrote:
Probably. My original loop is probably the best solution. I just
thought I'd throw this one out, because it is often a good solution;
it's one of the solutions which should come to mind immediately, but
I've seen far too many programmers who never think of it.
There are always so many things to think about :-) Even for a simple
function like this the following immediately come to mind:
* do you want adaptability (std::not1, etc.)? In that case you should
orient towards a functor, not a function
I think boost::bind has solved this problem.
* do you want it to work for floating point types as well?
In which case, of the algorithms already proposed, only the
table lookup works:-).
* and for UDTs?
Just to make the table generation a bit harder, right:-).
* and for bases other than two?
??? There's no dependancy on the base in the original problem.
The standard guarantees that integral types will have a base 2
representation. As for other types, all of the functions
available on floating points have a defined behavior regardless
of the base.
* do you want to consider modular arithmetic? Note that for an 8-bit
unsigned integer, 128 * 2 = 0, so you might well want to consider 0
a power of two (with exponent 8)
In general I tend to prefer robustness and flexibility over other
aspects (I want to write things once).
Robustness is the first requirement; if the function doesn't
work correctly for certain values, it's wrong.
Flexibility is more difficult: how do you know what types of
flexibility will be needed before the need arises. Premature
genericity is about like premature optimization.
[...]
As to the second goal (flexibility), adaptability and support for UDTs
would be very high in my list of design goals.
Why? How often have you had to deal with user defined numeric
types in your application? (I'm not saying that it is never
relevant, but as a general rule, it seems like a waste of time
in most environments.)
About the only genericity I'd worry about is making it work for
values other than 2. Until the need occured, of course.
But I don't want to
overgeneralize things, which leads to more complex tests and to code
having parts which are never exercised.
Agreed. Get a simple version working first, then add complexity
on an as needed basis.
For my amusement (and after seeing how many free software projects,
Linux, Mono, Mozilla Firefox, GNU coreutils, xmule and many others had
such a function) I sketched an implementation. You might want to
comment about it :-)
<http://breeze.svn.sourceforge.net/viewvc/breeze?view=rev&revision=46>
(I'm not satisfied of how much protection it offers about
signed/unsigned mismatch but as I as it's a sketch :-))
It gives a wrong result if called with a negative value. It
fails for UDT's for which is_integer is true, but which can't
convert to our_uintmax_t (whatever that is); for those with
lossy conversions, it gives wrong results. Roughly speaking:
template< uintmax_t N >
bool
is_power_of( uintmax_t i )
{
uintmax_t tmp = 1 ;
while ( tmp < i
&& tmp <= std::numeric_limits< uintmax_t >::max() /
N ) {
tmp *= N ;
}
return tmp == i ;
}
works in every case your template does, with the same results,
and is more generic, since it allows different powers. It's
probably worth adding a template parameter on the type, however,
to handle signed types correctly. Something like:
template< uintmax_t N, typename T >
bool
is_power_of( T i )
{
assert( N <= std::numeric_limits< T >::max() ) ;
T tmp = 1 ;
while ( tmp < i
&& tmp <= std::numeric_limits< T >::max() /
static_cast< T >( N ) ) {
tmp *= static_cast< T >( N ) ;
}
return tmp == i ;
}
(It would be nice if you could replace the assert with a
static_assert. I don't have Boost installed on this machine, so
I can't test it, but I rather suspect that the fact that max()
formally isn't a constant integral expression means that it
won't work. And of course, you don't want to inverse the order
of the template arguments, since you want to specify the first
explicitly, but not the second.)
--
James Kanze (Gabi Software) email: james.kanze@gmail.com
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]