CODEWITHSUNDEEP
gobytecomputer-sciencebit
jpincas
jpincas

Reputation: 35

Byte ordering of floats

I'm working on Tormenta (https://github.com/jpincas/tormenta) which is backed by BadgerDB (https://github.com/dgraph-io/badger). BadgerDB stores keys (slices of bytes) in byte order. I am creating keys which contain floats which need to be stored in order so I can user Badger's key iteration properly. I don't have a solid CS background so I'm a little out of my depth.

I encode the floats like this: binary.Write(buf, binary.BigEndian, myFloat). This works fine for positive floats - the key order is what you'd expect, but the byte ordering breaks down for negative floats.

As an aside, ints present the same problem, but I was able to fix that relatively easily by flipping the sign bit on the int with b[0] ^= 1 << 7 (where b is the []byte holding the result of encoding the int), and then flipping back when retrieving the key.

Although b[0] ^= 1 << 7 DOES also flip the sign bit on floats and thus places all the negative floats before the positive ones, the negative ones are incorrectly (backwards) ordered. It is necessary to flip the sign bit and reverse the order of the negative floats.

A similar question was asked on StackOverflow here: Sorting floating-point values using their byte-representation, and the solution was agreed to be:

XOR all positive numbers with 0x8000... and negative numbers with 0xffff.... This should flip the sign bit on both (so negative numbers go first), and then reverse the ordering on negative numbers.

However, that's way above my bit-flipping-skills level, so I was hoping a Go bit-ninja could help me translate that into some Go code.

Upvotes: 3

Views: 353

Answers (1)

icza
icza

Reputation: 418287

Using math.Float64bits()

You could use math.Float64bits() which returns an uint64 value having the same bytes / bits as the float64 value passed to it.

Once you have an uint64, performing bitwise operations on it is trivial:

f := 1.0 // Some float64 value

bits := math.Float64bits(f)
if f >= 0 {
    bits ^= 0x8000000000000000
} else {
    bits ^= 0xffffffffffffffff
}

Then serialize the bits value instead of the f float64 value, and you're done.

Let's see this in action. Let's create a wrapper type holding a float64 number and its bytes:

type num struct {
    f    float64
    data [8]byte
}

Let's create a slice of these nums:

nums := []*num{
    {f: 1.0},
    {f: 2.0},
    {f: 0.0},
    {f: -1.0},
    {f: -2.0},
    {f: math.Pi},
}

Serializing them:

for _, n := range nums {
    bits := math.Float64bits(n.f)
    if n.f >= 0 {
        bits ^= 0x8000000000000000
    } else {
        bits ^= 0xffffffffffffffff
    }
    if err := binary.Write(bytes.NewBuffer(n.data[:0]), binary.BigEndian, bits); err != nil {
        panic(err)
    }
}

This is how we can sort them byte-wise:

sort.Slice(nums, func(i int, j int) bool {
    ni, nj := nums[i], nums[j]
    for k := range ni.data {
        if bi, bj := ni.data[k], nj.data[k]; bi < bj {
            return true // We're certain it's less
        } else if bi > bj {
            return false // We're certain it's not less
        } // We have to check the next byte
    }
    return false // If we got this far, they are equal (=> not less)
})

And now let's see the order after byte-wise sorting:

fmt.Println("Final order byte-wise:")
for _, n := range nums {
    fmt.Printf("% .7f %3v\n", n.f, n.data)
}

Output will be (try it on the Go Playground):

Final order byte-wise:
-2.0000000 [ 63 255 255 255 255 255 255 255]
-1.0000000 [ 64  15 255 255 255 255 255 255]
 0.0000000 [128   0   0   0   0   0   0   0]
 1.0000000 [191 240   0   0   0   0   0   0]
 2.0000000 [192   0   0   0   0   0   0   0]
 3.1415927 [192   9  33 251  84  68  45  24]

Without math.Float64bits()

Another option would be to first serialize the float64 value, and then perform XOR operations on the bytes.

If the number is positive (or zero), XOR the first byte with 0x80, and the rest with 0x00, which is basically do nothing with them.

If the number is negative, XOR all the bytes with 0xff, which is basically a bitwise negation.

In action: the only part that is different is the serialization and XOR operations:

for _, n := range nums {
    if err := binary.Write(bytes.NewBuffer(n.data[:0]), binary.BigEndian, n.f); err != nil {
        panic(err)
    }
    if n.f >= 0 {
        n.data[0] ^= 0x80
    } else {
        for i, b := range n.data {
            n.data[i] = ^b
        }
    }
}

The rest is the same. The output will also be the same. Try this one on the Go Playground.

Upvotes: 3

Related Questions