Sort of administrative question :) I'm going to commit an improved version of dynamic_bitset, in the next days. The version, which is in the sandbox, has finally had Jeremy's approval. My question is: to implement find_first and find_next, two new functions I have added, I use a simple lowest_bit<T> template, which in turn requires integer_log2<T>; so there are two new header files: a) http://tinyurl.com/36zsj b) http://tinyurl.com/2lb26 I think they provide two useful facilities in themselves. Would it be ok to commit them in the boost/ folder? Or should they belong to boost/detail/? Or maybe boost/pending/? -- Genny.
Gennaro Prota <gennaro_prota@yahoo.com> writes:
Sort of administrative question :) I'm going to commit an improved version of dynamic_bitset, in the next days. The version, which is in the sandbox, has finally had Jeremy's approval. My question is: to implement find_first and find_next, two new functions I have added, I use a simple lowest_bit<T> template, which in turn requires integer_log2<T>; so there are two new header files:
a) http://tinyurl.com/36zsj b) http://tinyurl.com/2lb26
I think they provide two useful facilities in themselves. Would it be ok to commit them in the boost/ folder? Or should they belong to boost/detail/? Or maybe boost/pending/?
If they're going into boost/, they need to be documented. THat's the only constraint, IMO. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Sat, 13 Mar 2004 14:24:04 -0500, David Abrahams <dave@boost-consulting.com> wrote:
Gennaro Prota <gennaro_prota@yahoo.com> writes:
[two new header files:]
a) http://tinyurl.com/36zsj b) http://tinyurl.com/2lb26
I think they provide two useful facilities in themselves. Would it be ok to commit them in the boost/ folder? Or should they belong to boost/detail/? Or maybe boost/pending/?
If they're going into boost/, they need to be documented. THat's the only constraint, IMO.
Oh, no problem for that. But where the docs go? I mean: they are not a "library" in themselves; and "utility" seems too much an easy collector for everything :) PS: should I also ask for a mini-review? -- Genny.
Gennaro Prota <gennaro_prota@yahoo.com> writes:
[two new header files:]
a) http://tinyurl.com/36zsj b) http://tinyurl.com/2lb26
I think they provide two useful facilities in themselves. Would it be ok to commit them in the boost/ folder? Or should they belong to boost/detail/? Or maybe boost/pending/?
If they're going into boost/, they need to be documented. THat's the only constraint, IMO.
Oh, no problem for that. But where the docs go? I mean: they are not a "library" in themselves; and "utility" seems too much an easy collector for everything :)
These look to me like they should be part of http://www.boost.org/libs/integer/index.html, no?
PS: should I also ask for a mini-review?
Or at least consult Darlye Walker. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 4/11/04 10:34 PM, "David Abrahams" <dave@boost-consulting.com> wrote:
Gennaro Prota <gennaro_prota@yahoo.com> writes:
[two new header files:]
a) http://tinyurl.com/36zsj b) http://tinyurl.com/2lb26
I think they provide two useful facilities in themselves. Would it be ok to commit them in the boost/ folder? Or should they belong to boost/detail/? Or maybe boost/pending/?
If they're going into boost/, they need to be documented. THat's the only constraint, IMO.
Oh, no problem for that. But where the docs go? I mean: they are not a "library" in themselves; and "utility" seems too much an easy collector for everything :)
These look to me like they should be part of http://www.boost.org/libs/integer/index.html, no?
That seems like an OK place. Don't forget to update <boost/integer_fwd.hpp> too.
PS: should I also ask for a mini-review?
Probably.
Or at least consult Darlye Walker.
Question: are these functions really meant for any integer type, including user-defined ones? Or are they just for the built-in types? If the latter, couldn't you skip the templating by using the largest built-in type? (Promotions will handle the smaller built-in types.) int integer_log2( uintmax_t x ) { int result = 0; for ( int n = std::numeric_limits<uintmax_t>::digits - 1 ; x > 1u ; n /= 2 ) { if ( uintmax_t const t = x >> n ) { result += n; x = t; } } return result; } int lowest_bit( uintmax_t x ) { return integer_log2( x - (x & ( x - 1 )) ); } Maybe the two functions could share the same header. We don't need negative "x" values, since they don't have a defined (real) logarithm, and the bitwise operations may have strange results for them. We give a junk return for a zero-value argument instead of crashing. We could mention that using zero is undefined (just like negative values, but we can't get rid of it by switching to an unsigned type). Why does the "lowest_bit" function work? I can't see it. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Daryle Walker wrote:
int lowest_bit( uintmax_t x ) { return integer_log2( x - (x & ( x - 1 )) ); } [snip]
Why does the "lowest_bit" function work? I can't see it.
It looks to be using the property of (x & ( x - 1 ) having a value of 0 when x is a power of two *or when x is 0*, think binary... when x is a power of 2: [<leading zeros>] 1 [<trailing zeros>] then x - 1 becomes: [<leading zeros>] 0 [<trailing 1s>] thus (x & ( x - 1 ) is becomes 0 because no bit set in the original is still set after the subtract 1. This then means lowest_bit returns integer_log2( x - 0 ). In the case where there is more than a single bit set in x then x - 1 will still only affect the lowest bit set and the trailing zeros, thus the prefix is retained (x&x == x), so the statement ( x - (x & ( x - 1 )) ) subtracts off the upper bits that are set leaving you with a single bit (the lowest bit set) as above. So as long as you don't mind the results of x == 0 and x == 1 then your OK, Kevin -- | Kevin Wheatley | These are the opinions of | | Senior Do-er of Technical Things | nobody and are not shared | | Cinesite (Europe) Ltd | by my employers |
participants (4)
-
Daryle Walker -
David Abrahams -
Gennaro Prota -
Kevin Wheatley