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 [0]
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-[0] 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 [0] 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
versions).