Байтовое упорядочение поплавков

Question

Я работаю над Tormenta (https://github.com/jpincas/tormenta), который поддерживается BadgerDB (https://github.com/dgraph-io/badger). BadgerDB хранит ключи (куски байтов) в порядке байтов. Я создаю ключи, которые содержат числа с плавающей запятой, которые должныбыть сохраненным в порядке, чтобы я мог правильно использовать итерацию ключа Бэджера. У меня нет твердого фона CS, поэтому я немного не в себе.

Я кодирую поплавки следующим образом: binary.Write(buf, binary.BigEndian, myFloat).Это работает хорошо для положительных значений с плавающей точкой - ключевой порядок соответствует ожидаемому, но порядок следования байтов разбивается на отрицательные значения с плавающей точкой.

В качестве отступов, int представляет ту же проблему, но я смог это исправитьсравнительно легко, если перевернуть бит знака на int с помощью b[0] ^= 1 << 7 (где b - это []byte, содержащий результат кодирования int), а затем перевернуть обратно при получении ключа.

Хотя b[0] ^= 1 << 7 также переворачивает бит знака на поплавки и, таким образом, ставит все отрицательные поплавки перед положительными, отрицательные (в обратном порядке) упорядочены. Необходимо перевернуть знаковый битd обратный порядок отрицательных чисел с плавающей точкой.

Аналогичный вопрос был задан в отношении StackOverflow здесь: Сортировка значений с плавающей запятой по их байт-представлению , и было решено, что решение будет следующим:

XOR все положительные числа с 0x8000 ... и отрицательные числа с 0xffff .... Это должно перевернуть бит знака на обоих (так, чтобы отрицательные числа шли первыми), а затем изменить порядок на отрицательные числа.

Тем не менее, это намного выше моего уровня навыков работы с битами, поэтому я надеялся, что бит-ниндзя Go поможет мне перевести это в некоторый код Go.

Answer 1

Использование math.Float64bits()

Вы можете использовать math.Float64bits(), который возвращает значение uint64, имеющее те же байты / биты, что и значение float64, переданное ему.

Когда у вас есть 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 s:

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

Вывод будет(попробуйте на 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]

Без math.Float64bits()

Другой вариант - сначала сериализовать значение float64, а затем выполнитьОперации XOR над байтами.

Если число положительное (или ноль), XOR первый байт с 0x80, а остальные с 0x00, что в принципе ничего с ними не делает.

Если число отрицательное, XOR все байты с 0xff, что в основном является побитовым отрицанием.

В действии: единственная отличающаяся часть - операции сериализации и 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
        }
    }
}

Остальное тоже самое.Выход также будет таким же.Попробуйте это на Go Playground .