Topic: std::bitset::msb and std::bitset::lsb
Author: Dawid Pilarski <dawidpicpp@gmail.com>
Date: Thu, 20 Apr 2017 02:07:20 -0700 (PDT)
Raw View
------=_Part_6769_201372310.1492679240542
Content-Type: multipart/alternative;
boundary="----=_Part_6770_481458058.1492679240542"
------=_Part_6770_481458058.1492679240542
Content-Type: text/plain; charset=UTF-8
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
--
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-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/0e8816d3-6973-4dd8-89d5-1112415439f0%40isocpp.org.
------=_Part_6770_481458058.1492679240542
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Recently when dealing with some algorithms I had lots of n=
eed 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 b=
e improved with adding msb() and lsb() methods to the std::bitset class.<br=
><br>Compilers currently have their own builtins, that can compute followin=
g in a constant time, so implementation of msb and lsb methods could be eff=
icient and portable. Standard could simply say, that complexity of those op=
erations are O(n) or better.<br><br>Before doing anything further I would l=
ike to ask, whether this could be useful or doable (maybe I am missing some=
thing).<br><br>Thanks for sharing your thoughts.<br><br>Best regards,<br>Da=
wid<br></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/0e8816d3-6973-4dd8-89d5-1112415439f0%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/0e8816d3-6973-4dd8-89d5-1112415439f0=
%40isocpp.org</a>.<br />
------=_Part_6770_481458058.1492679240542--
------=_Part_6769_201372310.1492679240542--
.
Author: Dan Raviv <dan.raviv@gmail.com>
Date: Thu, 27 Apr 2017 13:16:32 -0700 (PDT)
Raw View
------=_Part_8_1681689751.1493324192524
Content-Type: multipart/alternative;
boundary="----=_Part_9_65330761.1493324192525"
------=_Part_9_65330761.1493324192525
Content-Type: text/plain; charset=UTF-8
+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
On Thursday, April 20, 2017 at 11:07:20 AM UTC+2, Dawid Pilarski wrote:
>
> 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
>
--
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-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/2e2fe905-e367-412d-a96f-88a8423912ac%40isocpp.org.
------=_Part_9_65330761.1493324192525
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">+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?<div><div><br></div><div>Cheers,</div><div>Dan<br><div><=
br>On Thursday, April 20, 2017 at 11:07:20 AM UTC+2, Dawid Pilarski wrote:<=
blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bord=
er-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">Recently when =
dealing with some algorithms I had lots of need to find msb and lsb in a bi=
tset, 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() an=
d lsb() methods to the std::bitset class.<br><br>Compilers currently have t=
heir own builtins, that can compute following in a constant time, so implem=
entation of msb and lsb methods could be efficient and portable. Standard c=
ould simply say, that complexity of those operations are O(n) or better.<br=
><br>Before doing anything further I would like to ask, whether this could =
be useful or doable (maybe I am missing something).<br><br>Thanks for shari=
ng your thoughts.<br><br>Best regards,<br>Dawid<br></div></blockquote></div=
></div></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/2e2fe905-e367-412d-a96f-88a8423912ac%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/2e2fe905-e367-412d-a96f-88a8423912ac=
%40isocpp.org</a>.<br />
------=_Part_9_65330761.1493324192525--
------=_Part_8_1681689751.1493324192524--
.
Author: "Vicente J. Botet Escriba" <vicente.botet@wanadoo.fr>
Date: Thu, 27 Apr 2017 23:22:22 +0200
Raw View
Le 20/04/2017 =C3=A0 11:07, Dawid Pilarski a =C3=A9crit :
> Recently when dealing with some algorithms I had lots of need to find=20
> msb and lsb in a bitset, but there is no portable way to count them=20
> (except own implementation with O(n) complexity). I think this could=20
> be improved with adding msb() and lsb() methods to the std::bitset class.
>
> Compilers currently have their own builtins, that can compute=20
> following in a constant time, so implementation of msb and lsb methods=20
> could be efficient and portable. Standard could simply say, that=20
> complexity of those operations are O(n) or better.
I believe we need to have (constant?) access to the array of blocks (a=20
span?). Why it is preferable to work on this array? Because we can have=20
other types that need this kind of information independently of whether=20
it represents a bit set or big integer.
This doesn't mean that we don't need algorithm msb, lsb, that iterates=20
over this array.
This should be an extension to=20
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0553r1.html
My 2 cts,
Vicente
--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@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.f=
r.
.
Author: Dawid Pilarski <dawidpicpp@gmail.com>
Date: Thu, 4 May 2017 19:55:13 +0200
Raw View
--001a1148db1c8cd544054eb67956
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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
2017-04-27 23:22 GMT+02:00 Vicente J. Botet Escriba <
vicente.botet@wanadoo.fr>:
> Le 20/04/2017 =C3=A0 11:07, Dawid Pilarski a =C3=A9crit :
>
>> Recently when dealing with some algorithms I had lots of need to find ms=
b
>> 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 wit=
h
>> 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 th=
ose
>> 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 i=
t
> 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/s
> c22/wg21/docs/papers/2017/p0553r1.html
>
> My 2 cts,
> Vicente
>
> --
> 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-proposals@isocpp.org.
> To view this discussion on the web visit https://groups.google.com/a/is
> ocpp.org/d/msgid/std-proposals/896bab52-05d1-9e8b-5230-
> 1661449946fb%40wanadoo.fr.
>
--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAOkZZiEJJgL%3DUr425YkuW62AP%3Dq1JFBFZAvgZ_cM6ya=
H6H2zXg%40mail.gmail.com.
--001a1148db1c8cd544054eb67956
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">My apologies for absence.<br><br>Thank you for your feedba=
ck. I will take it all in my considerations and I will try to write somethi=
ng about it ASAP.<br><br>Thank you once again,<br>Dawid Pilarski</div><div =
class=3D"gmail_extra"><br><div class=3D"gmail_quote">2017-04-27 23:22 GMT+0=
2:00 Vicente J. Botet Escriba <span dir=3D"ltr"><<a href=3D"mailto:vicen=
te.botet@wanadoo.fr" target=3D"_blank">vicente.botet@wanadoo.fr</a>></sp=
an>:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border=
-left:1px #ccc solid;padding-left:1ex"><span class=3D"">Le 20/04/2017 =C3=
=A0 11:07, Dawid Pilarski a =C3=A9crit :<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Recently when dealing with some algorithms I had lots of need to find msb a=
nd 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 a=
dding msb() and lsb() methods to the std::bitset class.<br>
<br>
Compilers currently have their own builtins, that can compute following in =
a constant time, so implementation of msb and lsb methods could be efficien=
t and portable. Standard could simply say, that complexity of those operati=
ons are O(n) or better.<br>
</blockquote></span>
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 t=
ypes that need this kind of information independently of whether it represe=
nts a bit set or big integer.<br>
This doesn't mean that we don't need algorithm msb, lsb, that itera=
tes over this array.<br>
This should be an extension to <a href=3D"http://www.open-std.org/jtc1/sc22=
/wg21/docs/papers/2017/p0553r1.html" rel=3D"noreferrer" target=3D"_blank">h=
ttp://www.open-std.org/jtc1/s<wbr>c22/wg21/docs/papers/2017/p055<wbr>3r1.ht=
ml</a><br>
<br>
My 2 cts,<br>
Vicente<span class=3D""><br>
<br>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isoc<wbr>pp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br></span>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/896bab52-05d1-9e8b-5230-1661449946fb%=
40wanadoo.fr" rel=3D"noreferrer" target=3D"_blank">https://groups.google.co=
m/a/is<wbr>ocpp.org/d/msgid/std-proposals<wbr>/896bab52-05d1-9e8b-5230-<wbr=
>1661449946fb%40wanadoo.fr</a>.<br>
</blockquote></div><br></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAOkZZiEJJgL%3DUr425YkuW62AP%3Dq1JFBF=
ZAvgZ_cM6yaH6H2zXg%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter"=
>https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOkZZiEJJgL%=
3DUr425YkuW62AP%3Dq1JFBFZAvgZ_cM6yaH6H2zXg%40mail.gmail.com</a>.<br />
--001a1148db1c8cd544054eb67956--
.