------=_Part_1789_1179661129.1439991192478
Content-Type: multipart/alternative;
 boundary="----=_Part_1790_168313116.1439991192478"

------=_Part_1790_168313116.1439991192478
Content-Type: text/plain; charset=UTF-8

Sometimes it can be useful to check whether or not an std::bitset
"contains" another std::bitset.
Bitset *A contains *bitset *B *if *all bits set to 1 in B are *also* set to
1 in A.*

This can currently be verified by the following code:
if((a & b) == b) { /* a contains b */ }

The code written above *cannot make use of short-circuiting *in case of
multi-word bitsets.
A dedicated function could allow implementation to take advantage of
short-circuiting.
Example:
for(auto i = 0; i < wordCount; ++i)
    if(bWords[i] & ~(aWords[i]) != 0)
        return false;

return true;

(Check this old StackOverflow question
<http://stackoverflow.com/questions/19258598/check-if-a-bitset-contains-all-values-of-another-bitset> for
more details.)

Thoughts?
(Could a proposal for this be accepted?)

--

---
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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_1790_168313116.1439991192478
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><font color=3D"#000000">Sometimes it can be useful to chec=
k whether or not an std::bitset &quot;contains&quot; another std::bitset.<b=
r>Bitset <b>A contains </b>bitset <b>B </b>if <b>all bits set to 1 in B are=
 </b>also<b> set to 1 in A.</b></font><div><font color=3D"#000000"><b><br><=
/b></font></div><div><font color=3D"#000000">This can currently be verified=
 by the following code:</font></div><div><div class=3D"prettyprint" style=
=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-word; background=
-color: rgb(250, 250, 250);"><code class=3D"prettyprint"><div class=3D"subp=
rettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">if</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">((</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify">a </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&amp;</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> b</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">=3D=3D</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> b</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><font =
color=3D"#880000"><span style=3D"color: #000;" class=3D"styled-by-prettify"=
> </span><span style=3D"color: #800;" class=3D"styled-by-prettify">/* a con=
tains b */</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><=
/font></div></code></div><br>The code written above <b>cannot make use of s=
hort-circuiting=C2=A0</b>in case of multi-word bitsets.</div><div>A dedicat=
ed function could allow implementation to take advantage of short-circuitin=
g.</div><div>Example:</div><div><div class=3D"prettyprint" style=3D"border:=
 1px solid rgb(187, 187, 187); word-wrap: break-word; background-color: rgb=
(250, 250, 250);"><code class=3D"prettyprint"><div class=3D"subprettyprint"=
><font color=3D"#660066"><div class=3D"subprettyprint">for(auto i =3D 0; i =
&lt; wordCount; ++i)</div><div class=3D"subprettyprint">=C2=A0 =C2=A0 if(bW=
ords[i] &amp; ~(aWords[i]) !=3D 0)</div><div class=3D"subprettyprint">=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 return false;</div><div class=3D"subprettyprint"><=
br></div><div class=3D"subprettyprint">return true;</div></font></div></cod=
e></div><br>(Check this=C2=A0<a href=3D"http://stackoverflow.com/questions/=
19258598/check-if-a-bitset-contains-all-values-of-another-bitset">old Stack=
Overflow question</a>=C2=A0for more details.)<br><br>Thoughts?<br>(Could a =
proposal for this be accepted?)</div></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; 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 />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_1790_168313116.1439991192478--
------=_Part_1789_1179661129.1439991192478--

.

------=_Part_2174_2020757414.1440018651649
Content-Type: multipart/alternative;
 boundary="----=_Part_2175_1292206138.1440018651650"

------=_Part_2175_1292206138.1440018651650
Content-Type: text/plain; charset=UTF-8



On Wednesday, August 19, 2015 at 3:33:12 PM UTC+2, Vittorio Romeo wrote:
>
> Sometimes it can be useful to check whether or not an std::bitset
> "contains" another std::bitset.
> Bitset *A contains *bitset *B *if *all bits set to 1 in B are *also* set
> to 1 in A.*
>
> This can currently be verified by the following code:
> if((a & b) == b) { /* a contains b */ }
>
> The code written above *cannot make use of short-circuiting *in case of
> multi-word bitsets.
> A dedicated function could allow implementation to take advantage of
> short-circuiting.
> Example:
> for(auto i = 0; i < wordCount; ++i)
>     if(bWords[i] & ~(aWords[i]) != 0)
>         return false;
>
> return true;
>
> (Check this old StackOverflow question
> <http://stackoverflow.com/questions/19258598/check-if-a-bitset-contains-all-values-of-another-bitset> for
> more details.)
>
> Thoughts?
> (Could a proposal for this be accepted?)
>

Similar functionality has been propsed before in N2050
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf>, but in
the context of dynamic bitsets. It essentially proposed a slightly extended
version of boost::dynamic_bitset, including member functions is_subset_of()
and is_proper_subset_of(), as well as the superset versions. I don't think
that proposal had any follow-through however.

However, adding those members would only solve this particular problem. It
would be much more convenient if std::bitset would mimic std::vector and
expose a data() pointer to its unsigned integer blocks. This would allow
e.g. library writers to provide expression templates that facilitate loop
fusion and eliminate temporaries in multi-term bit-twiddling expressions
for bitsets with more than 64-bits.

--

---
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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_2175_1292206138.1440018651650
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<br><br>On Wednesday, August 19, 2015 at 3:33:12 PM UTC+2, Vittorio Romeo w=
rote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><font co=
lor=3D"#000000">Sometimes it can be useful to check whether or not an std::=
bitset &quot;contains&quot; another std::bitset.<br>Bitset <b>A contains </=
b>bitset <b>B </b>if <b>all bits set to 1 in B are </b>also<b> set to 1 in =
A.</b></font><div><font color=3D"#000000"><b><br></b></font></div><div><fon=
t color=3D"#000000">This can currently be verified by the following code:</=
font></div><div><div style=3D"border:1px solid rgb(187,187,187);word-wrap:b=
reak-word;background-color:rgb(250,250,250)"><code><div><span style=3D"colo=
r:#008">if</span><span style=3D"color:#660">((</span><span style=3D"color:#=
000">a </span><span style=3D"color:#660">&amp;</span><span style=3D"color:#=
000"> b</span><span style=3D"color:#660">)</span><span style=3D"color:#000"=
> </span><span style=3D"color:#660">=3D=3D</span><span style=3D"color:#000"=
> b</span><span style=3D"color:#660">)</span><span style=3D"color:#000"> </=
span><span style=3D"color:#660">{</span><font color=3D"#880000"><span style=
=3D"color:#000"> </span><span style=3D"color:#800">/* a contains b */</span=
><span style=3D"color:#000"> </span><span style=3D"color:#660">}</span></fo=
nt></div></code></div><br>The code written above <b>cannot make use of shor=
t-circuiting=C2=A0</b>in case of multi-word bitsets.</div><div>A dedicated =
function could allow implementation to take advantage of short-circuiting.<=
/div><div>Example:</div><div><div style=3D"border:1px solid rgb(187,187,187=
);word-wrap:break-word;background-color:rgb(250,250,250)"><code><div><font =
color=3D"#660066"><div>for(auto i =3D 0; i &lt; wordCount; ++i)</div><div>=
=C2=A0 =C2=A0 if(bWords[i] &amp; ~(aWords[i]) !=3D 0)</div><div>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 return false;</div><div><br></div><div>return true;</div>=
</font></div></code></div><br>(Check this=C2=A0<a href=3D"http://stackoverf=
low.com/questions/19258598/check-if-a-bitset-contains-all-values-of-another=
-bitset" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39=
;http://www.google.com/url?q\75http%3A%2F%2Fstackoverflow.com%2Fquestions%2=
F19258598%2Fcheck-if-a-bitset-contains-all-values-of-another-bitset\46sa\75=
D\46sntz\0751\46usg\75AFQjCNG6PeS3H8JGrpCdWPdyqKw8CWbPQw&#39;;return true;"=
 onclick=3D"this.href=3D&#39;http://www.google.com/url?q\75http%3A%2F%2Fsta=
ckoverflow.com%2Fquestions%2F19258598%2Fcheck-if-a-bitset-contains-all-valu=
es-of-another-bitset\46sa\75D\46sntz\0751\46usg\75AFQjCNG6PeS3H8JGrpCdWPdyq=
Kw8CWbPQw&#39;;return true;">old StackOverflow question</a>=C2=A0for more d=
etails.)<br><br>Thoughts?<br>(Could a proposal for this be accepted?)</div>=
</div></blockquote><div><br></div><div>Similar functionality has been props=
ed before in <a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/=
2006/n2050.pdf">N2050</a>, but in the context of dynamic bitsets. It essent=
ially proposed a slightly extended version of boost::dynamic_bitset, includ=
ing member functions is_subset_of() and is_proper_subset_of(), as well as t=
he superset versions. I don&#39;t think that proposal had any follow-throug=
h however.</div><div><br></div><div>However, adding those members would onl=
y solve this particular problem. It would be much more convenient if std::b=
itset would mimic std::vector and expose a data() pointer to its unsigned i=
nteger blocks. This would allow e.g. library writers to provide expression =
templates that facilitate loop fusion and eliminate temporaries in multi-te=
rm bit-twiddling expressions for bitsets with more than 64-bits.=C2=A0</div=
>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; 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 />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_2175_1292206138.1440018651650--
------=_Part_2174_2020757414.1440018651649--

.

--Apple-Mail=_029CDFBB-BED5-4B2E-AE75-885028852EF4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9308=E2=80=9320, at 5:10 AM, rhalbersma@gmail.com wrote:
>=20
> However, adding those members would only solve this particular problem. I=
t would be much more convenient if std::bitset would mimic std::vector and =
expose a data() pointer to its unsigned integer blocks. This would allow e.=
g. library writers to provide expression templates that facilitate loop fus=
ion and eliminate temporaries in multi-term bit-twiddling expressions for b=
itsets with more than 64-bits.=20

The expression (a & b).any() already optimized perfectly: http://goo.gl/Gnd=
tKj <http://goo.gl/GndtKj> (godbolt.org)

Implementations have latitude to use underlying types smaller than unsigned=
 long, so the return type of data() would be implementation-dependent. Prob=
ably its bit ordering, too.

--=20

---=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

--Apple-Mail=_029CDFBB-BED5-4B2E-AE75-885028852EF4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9308=
=E2=80=9320, at 5:10 AM, <a href=3D"mailto:rhalbersma@gmail.com" class=3D""=
>rhalbersma@gmail.com</a> wrote:</div><br class=3D"Apple-interchange-newlin=
e"><div class=3D""><span style=3D"font-family: Helvetica; font-size: 12px; =
font-style: normal; font-variant: normal; font-weight: normal; letter-spaci=
ng: normal; line-height: normal; orphans: auto; text-align: start; text-ind=
ent: 0px; text-transform: none; white-space: normal; widows: auto; word-spa=
cing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !im=
portant;" class=3D"">However, adding those members would only solve this pa=
rticular problem. It would be much more convenient if std::bitset would mim=
ic std::vector and expose a data() pointer to its unsigned integer blocks. =
This would allow e.g. library writers to provide expression templates that =
facilitate loop fusion and eliminate temporaries in multi-term bit-twiddlin=
g expressions for bitsets with more than 64-bits.&nbsp;</span></div></block=
quote></div><br class=3D""><div class=3D"">The expression <font face=3D"Cou=
rier" class=3D"">(a &amp; b).any()</font>&nbsp;already optimized perfectly:=
&nbsp;<a href=3D"http://goo.gl/GndtKj" class=3D"">http://goo.gl/GndtKj</a>&=
nbsp;(<a href=3D"http://godbolt.org" class=3D"">godbolt.org</a>)</div><div =
class=3D""><br class=3D""></div><div class=3D"">Implementations have latitu=
de to use underlying types smaller than unsigned long, so the return type o=
f <font face=3D"Courier" class=3D"">data()</font> would be implementation-d=
ependent. Probably its bit ordering, too.</div></body></html>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; 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 />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--Apple-Mail=_029CDFBB-BED5-4B2E-AE75-885028852EF4--

.

--Apple-Mail=_187E0661-3ABC-47B5-8B24-A7094BD0EBF4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9308=E2=80=9320, at 7:48 AM, David Krauss <potswa@mac.com> =
wrote:
>=20
> The expression (a & b).any() already optimized perfectly: http://goo.gl/G=
ndtKj <http://goo.gl/GndtKj> (godbolt.org <http://godbolt.org/>)


Ah, never mind, for larger bitsets GCC and Clang still emit two loops conne=
cted by a big ol=E2=80=99 temporary on the stack.

(And, the expression should be ! (~a & b).any(), per Vittorio=E2=80=99s sec=
ond snippet. Both seem equally intractable to loop fusion.)

--=20

---=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

--Apple-Mail=_187E0661-3ABC-47B5-8B24-A7094BD0EBF4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9308=
=E2=80=9320, at 7:48 AM, David Krauss &lt;<a href=3D"mailto:potswa@mac.com"=
 class=3D"">potswa@mac.com</a>&gt; wrote:</div><br class=3D"Apple-interchan=
ge-newline"><div class=3D""><div class=3D"" style=3D"font-family: Helvetica=
; font-size: 12px; font-style: normal; font-variant: normal; font-weight: n=
ormal; letter-spacing: normal; line-height: normal; orphans: auto; text-ali=
gn: start; text-indent: 0px; text-transform: none; white-space: normal; wid=
ows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">The expressi=
on<span class=3D"Apple-converted-space">&nbsp;</span><font face=3D"Courier"=
 class=3D"">(a &amp; b).any()</font>&nbsp;already optimized perfectly:&nbsp=
;<a href=3D"http://goo.gl/GndtKj" class=3D"">http://goo.gl/GndtKj</a>&nbsp;=
(<a href=3D"http://godbolt.org/" class=3D"">godbolt.org</a>)</div></div></b=
lockquote></div><div class=3D""><br class=3D""></div><div class=3D"">Ah, ne=
ver mind, for larger bitsets GCC and Clang still emit two loops connected b=
y a big ol=E2=80=99 temporary on the stack.</div><br class=3D""><div class=
=3D"">(And, the expression should be <font face=3D"Courier" class=3D"">! (~=
a &amp; b).any()</font>, per Vittorio=E2=80=99s second snippet. Both seem e=
qually intractable to loop fusion.)</div><div class=3D""><br class=3D""></d=
iv></body></html>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; 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 />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--Apple-Mail=_187E0661-3ABC-47B5-8B24-A7094BD0EBF4--

.