Re: function to determine if an integer is divisible by 2
Gennaro Prota wrote:
On Sun, 11 Feb 2007 12:59:33 CST, James Kanze wrote:
Incidentally I really hope vendors will catch up quickly with the
standard, or we'll begin using the new stuff at some time around 2012
:-/
It probably depends. They'll implement the new stuff that they
like, and ignore what they don't feel like implementing, just
like they did with the last version.
* 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:-).
Are you sure?
Not 100%, but it's certainly the easiest to be sure about.
I had in mind to use C99's log2 function (actually, the
corresponding three C++ overloads). Of course I don't have it/them on
current implementations, so I could either postpone support for
built-in floating points or write log2 myself. In any case the idea
was to check that the result of log2 was "integer" via modf.
I'm not familiar with log2, but what makes you think that it is
immune to rounding errors, say on a machine with base 10
floating point?
[...]
Robustness is the first requirement; if the function doesn't work
correctly for certain values, it's wrong.
By "robustness" I mean something stronger than "correctness": a robust
function (or class, or any other facility) is hard to be misused and
unlikely to stop working when modified for whatever reasons.
Agreed. But if it isn't correct to begin with, it isn't robust
either. I agree that it shouldn't give wrong results when
called with a negative value.
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.
Agreed. But I'm very oriented toward libraries. Almost everything I
need in an application ends up in some sort of reusable solution,
inevitably with some (hopefully reasonable) generalization. Of course
the boundary between reasonableness and "excess" is personal: you
generalized is_power_of_two to is_power_of_n, for instance, and
someone else might find that useless.
The point is that you don't decide which generalization to
implement until you actually need it. You write a simple,
non-template non-generic function: is_power_of_2( int ), and
that's it, until you need more. Then you modify as needed.
More generally, I think almost any library carries on some
generalization which didn't arise from a real need.
A lot of libraries I've seen also carry around a lot of dead
weight, to support genericity that is never used.
Sometimes there are features which are just there for
orthogonality (say is_enum<> in a type_traits library; have
you ever used that? :-)) and sometimes there are "just in
case" features. Even the standard libraries has examples of
things meant to allow generalization --custom manipulators for
instance-- which then don't work very well in practice
probably because they were standardized without having
actually been used.
The standard doesn't have custom manipulators---if they're in
the standard, they aren't custom:-). The standard does support
them pretty well, however; I don't think I've ever written an
application which didn't make extensive use of them.
[...]
About the only genericity I'd worry about is making it work for
values other than 2. Until the need occured, of course.
I don't disagree, but after a Google Code Search I decided to postpone
this one. Except for a very few uses of "is_power_of_4" I couldn't
find anything else than "is_power_of_2". And of course for the case
n==2 using the bitwise trick is about the only way to convince people
to use my implementation :-) More seriously I suspect it can be a
noticeable optimization in contexts such as reiserfs (not tried,
though).
I agree that the only is_power_of_n I've ever needed was 2. But
then, I've never needed it except as a compile time constant
either.
[...]
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 ;
}
Just to compare our styles I'd instinctively write the body as:
{
BREEZE_STATIC_ASSERT( base > 1, "precondition" );
const T b( base );
BREEZE_ASSERT( x >= b || x == 1 );
const T limit( x / b );
T candidate( 1 );
while( candidate <= limit )
candidate *= b;
return candidate == x;
}
In other words, I have to learn a whole new programming language
(BREEZE) in order to understand you code. (I'm supposing that
you've used base instead my N, and x instead of my i. In which
case, BREEZE_ASSERT can't do what I'd expect, or you'd get
assertion failures for any number of legitimate arguments.
Things like is_power_of< 3 >( 2 ).)
One difference is that, as paranoid as I am, I prefer initializing a
variable (limit, in this case) to a static_cast when that is possible.
Other differences are rather marginal.
It's not quite the same thing. I do the division in type T, you
do it in the type of N (base), which is uintmax_t. I cast
before the division, intentionally. (And of course, I have an
assert at the beginning to ensure that the cast is safe.) I
think your initialization is safe, however, since the results
cannot be greater than x (which is a positive value of type T).
(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.
You can easily get min and max for built-in types as constant
expressions. I have that (not committed) and it was also proposed for
boost, under general disinterest :-) The "easiest" way is to just
follow a "brute force" attack of the kind:
template< typename T > class max;
template<> class max< int > { static const int value = INT_MAX; }
template<> const int max<int>::value;
.... /* a specialization for each built-in type... */
Of course Bjarne Stroustrup's generalized constant expressions will
render this dance unnecessary.
That's something I'm waiting for. (I'm really not quite sure
why max() and min() are functions here anyway.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, 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! ]