Subject: Re: [boost] [dynamic_bitset] Comparison operators without assertions
From: Gavin Lambert (gavinl_at_[hidden])
Date: 2017-05-17 01:54:29
On 17/05/2017 12:39, Edward Diener wrote:
> On 5/16/2017 7:33 PM, Gavin Lambert wrote:
>> What's wrong with comparing bit-by-bit up to the common length, then
>> if still equal, whichever is longer is greater?
> It depends on what you consider the bits comprising the common length ?
> I am assuming you are considering the bits comprising the common length
> as the lower order bits comprising the common length. So that with
> 1010001 and 111
> the bits comprising the common length are 001 and 111.
I'm not thinking of it as a bitstring at all. Whichever bit is bit 
is compared first. It doesn't matter whether this is rendered first or
last as a bitstring.
(Although yes, I would expect it to be rendered last, because I've been
biased by little-bit-endian numbering; note that isn't universal,
however; albeit nearly so, even on big-endian-integer architectures, due
to base numbering.)
> However even if you mean the low order bits comprising the common
> length then by your suggestion 1010001 is still < 111, which again
> makes no sense.
Why does that make no sense? This is not a number and it is not a
bitstring, it is an arbitrary set of bits. As long as the ordering is
consistent (which this is, in all cases) it doesn't have to match how it
would be ordered as a bitstring or integer.
Some alternate completely different possible orderings:
1. Render it as a bitstring first and then use string comparison.
This seems needlessly perf-hungry (unless internal storage were already
as a bitstring, but that seems needlessly storage-hungry). This also
biases the comparison to the non- end, which might be good or bad
depending on usage.
2. Compare each 32-bit (or whatever window size is convenient) group
of bits as an unsigned integer (zero-padding if smaller than the window
size), starting at whichever one holds  and continuing as long as
both sets contributed at least one "real" bit to the window; if any
comparison returns unequal, that's the result; if all comparisons return
equal, then finally compare the actual sizes of both sets for the final
result. Advantage: fast. Disadvantage: the ordering might change if
the window size changes (eg. for different platforms, or future Boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk