std::bitset::msb and std::bitset::lsb

[Dawid Pilarski]

Recently when dealing with some algorithms I had lots of need to find msb and lsb in a bitset, but there is no portable way to count them (except own implementation with O(n) complexity). I think this could be improved with adding msb() and lsb() methods to the std::bitset class.

Compilers currently have their own builtins, that can compute following in a constant time, so implementation of msb and lsb methods could be efficient and portable. Standard could simply say, that complexity of those operations are O(n) or better.

Before doing anything further I would like to ask, whether this could be useful or doable (maybe I am missing something).

Thanks for sharing your thoughts.

Best regards,
Dawid

[Dan Raviv]

+1, sounds useful and basic enough to me. Perhaps you can write some details about the case in which you used std::bitset and needed this functionality?

Cheers,

Dan

[Vicente J. Botet Escriba]

Le 20/04/2017 à 11:07, Dawid Pilarski a écrit :
> Recently when dealing with some algorithms I had lots of need to find
> msb and lsb in a bitset, but there is no portable way to count them
> (except own implementation with O(n) complexity). I think this could
> be improved with adding msb() and lsb() methods to the std::bitset class.
>
> Compilers currently have their own builtins, that can compute
> following in a constant time, so implementation of msb and lsb methods
> could be efficient and portable. Standard could simply say, that
> complexity of those operations are O(n) or better.

I believe we need to have (constant?) access to the array of blocks (a
span?). Why it is preferable to work on this array? Because we can have
other types that need this kind of information independently of whether
it represents a bit set or big integer.
This doesn't mean that we don't need algorithm msb, lsb, that iterates
over this array.
This should be an extension to
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0553r1.html

My 2 cts,
Vicente

[Dawid Pilarski]

My apologies for absence.

Thank you for your feedback. I will take it all in my considerations and I will try to write something about it ASAP.

Thank you once again,
Dawid Pilarski

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/896bab52-05d1-9e8b-5230-1661449946fb%40wanadoo.fr.