Re: [boost] [dynamic_bitset] Comparison operators without assertions

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).