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