CODEWITHSUNDEEP
algorithm
Siderite Zackwehdex
Siderite Zackwehdex

Reputation: 6570

Efficiently transform float and double values into bytes that preserve the comparison relationship between values

I need a method by which to efficiently translate any float or double value to an array of bytes so that it preserves the comparison relationship to any other value.

Example: V1 and V2 are turned into arrays A1 and A2. If A1[0]<A2[0], then V1 must be smaller than V2. Same for larger. If A1[0]==A2[0] and A1[1]>A2[1] then V1 must be larger than V2. And so on. If all the bytes are the same, then the values V1 and V2 must be equal.

For a four byte integer I, an array that would satisfy the above condition would be [U>>24, (U>>16)&255, (U>>8)&255, U&255], where U is the uint positive value V-int.MinValue.

Since doubles are stored as 8 bytes, I expect something close to 8 bytes.

Do you think such a thing can be achieved? Thanks!

C# solution is preferred.

Upvotes: 0

Views: 124

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59184

The standard representation for doubles and floats that is used by most languages, IEEE 754, is already very close to supporting this requirement.

In C#, you can use BitConverter.DoubleToInt64Bits or SingleToInt32Bits to get the underlying bits of a double or float directly as an integer.

In order to make comparisons work out right, you only have to fix up the way negative numbers are handled:

long bits = BitConverter.DoubleToInt64Bits( theDouble );
if (bits < 0L) {
    bits ^= Int64.MaxValue;
}

The resulting longs will then have the same numeric order as the corresponding doubles. This works for all values except Nan, which isn't really comparable to anything else. The infinities, +0.0 and -0.0 work fine.

If you want +0.0 and -0.0 to have the same value, you can do this:

long bits = BitConverter.DoubleToInt64Bits( theDouble );
if (bits < 0L) {
    bits = (bits^Int64.MaxValue)+1L;
}

Note that if you want to make your byte array, you'll probably want to convert to an unsigned integer. You need to flip the sign bit if you want to preserve the ordering, or just do it like this:

long bits = BitConverter.DoubleToInt64Bits( theDouble );
ulong arraybits;
if (bits >= 0L) {
    arraybits = (1UL<<63) + (ulong)bits;
} else {
    arraybits = (ulong)~bits;
}

Upvotes: 1

Related Questions