浮动字节排序

Question

我正在研究Tormenta (https://github.com/jpincas/tormenta)，它是由BadgerDB (https://github.com/dgraph-io/badger)支持的。BadgerDB按字节顺序存储键(字节片)。我正在创建键，其中包含浮点数，需要按顺序存储，这样我才能正确地使用Badger的键迭代。我没有一个坚实的CS背景，所以我有点超出了我的深度。

我对浮标进行了如下编码：binary.Write(buf, binary.BigEndian, myFloat)。这对于正浮点数很好--关键的顺序是您所期望的，但是对于负浮点数，字节顺序会分解。

顺便说一下，int也存在同样的问题，但是我能够相对轻松地修复这个问题，方法是使用b[0] ^= 1 << 7 (其中b是保存int编码结果的[]byte )翻转int上的符号位，然后在检索密钥时翻转返回。

虽然b[0] ^= 1 << 7也会在浮点数上翻转符号位，因此将所有的负浮点数放在正浮点数之前，但是负值的排序是错误的(向后)。必须翻转符号位并反转负浮点数的顺序。

在StackOverflow上提出了一个类似的问题：使用其字节表示对浮点值进行排序。，并商定了以下解决方案：

所有正数都是0x8000..。负数带0 0xffff..。这应该同时翻转两个数字上的符号位(因此负数先取)，然后反转负数的顺序。

然而，这远远超出了我的技术水平，所以我希望一个Go位忍者能帮我把它翻译成一些Go代码。

Answer 1

使用math.Float64bits()

您可以使用math.Float64bits()，它返回一个具有与传递给它的float64值相同的字节/位的uint64值。

一旦您有了一个uint64，对其执行按位操作是非常简单的：

f := 1.0 // Some float64 value

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

然后序列化bits值而不是f float64值，您就完成了。

让我们看看这件事的效果。让我们创建一个包含float64数字及其字节的包装器类型：

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

让我们创建这些num的一部分：

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

序列化：

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

这就是我们如何按字节进行排序的方法：

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

现在让我们看看按字节顺序排序的顺序：

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

输出将是(在围棋游乐场上尝试)：

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]

无math.Float64bits()

另一个选项是首先序列化float64值，然后对字节执行XOR操作。

如果数字为正(或零)，则XOR为第一个字节( 0x80 )，其余字节为0x00 (基本上对它们不起任何作用)。

如果数字为负数，则使用0xff对所有字节进行XOR，这基本上是按位否定的。

实际操作:唯一不同的部分是序列化和XOR操作：

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
        }
    }
}

其余的都一样。输出也将是相同的。在围棋游乐场上试试这个。