将big.Int转换为[2]int64,反之亦然,并进行二进制补码转换。

huangapple go评论69阅读模式
英文:

Converting big.Int to [2]int64, vice-versa and two's complement

问题

我正在尝试将Go的big.Int转换为[2]int64,以表示一个128位整数。目的是为了能够匹配Rust的i128::to_le_bytes()函数,该函数将128位有符号整数编码为小端字节顺序。这个示例与Rust的i128::to_le_bytes()函数相匹配。但是,当我尝试将其转换回big.Int时,得到的值并不相同。在进行初始右移时是否丢失了某些位?谢谢。

package main
 
import (
	"encoding/binary"
	"fmt"
	"math/big"
)
 
func main() {
	initial := new(big.Int)
	initial.SetString("-42", 10)
 
	value, _ := new(big.Int).SetString("-42", 10)
 
	var result [2]int64
 
	result[0] = value.Int64()
	result[1] = value.Rsh(value, 64).Int64()
 
	leRepresentation := make([]byte, 16)
 
	binary.LittleEndian.PutUint64(leRepresentation[:8], uint64(result[0]))
	binary.LittleEndian.PutUint64(leRepresentation[8:], uint64(result[1]))
 
	fmt.Println(leRepresentation)
 
	fmt.Println(result)
 
	reverse := big.NewInt(result[1])
	reverse.Lsh(reverse, 64)
	reverse.Add(reverse, big.NewInt(result[0]))
 
	fmt.Println(reverse.String())
 
	fmt.Println(initial.String() == reverse.String())
}
英文:

I am trying to convert Go big.Int, which will represent a 128-bit integer to [2]int64. The idea is to be able to match Rust's i128::to_le_bytes(), which encodes 128-bit signed integer into little-endian byte order. The example matches Rust's i128::to_le_bytes(). Whenever I try to convert it back to big.Int, I do not get the same value. Is there any bit lost when doing the initial right shift? Thanks.

package main
 
import (
	"encoding/binary"
	"fmt"
	"math/big"
)
 
func main() {
	initial := new(big.Int)
	initial.SetString("-42", 10)
 
	value, _ := new(big.Int).SetString("-42", 10)
 
	var result [2]int64
 
	result[0] = value.Int64()
	result[1] = value.Rsh(value, 64).Int64()
 
	leRepresentation := make([]byte, 16)
 
	binary.LittleEndian.PutUint64(leRepresentation[:8], uint64(result[0]))
	binary.LittleEndian.PutUint64(leRepresentation[8:], uint64(result[1]))
 
	fmt.Println(leRepresentation)
 
	fmt.Println(result)
 
	reverse := big.NewInt(result[1])
	reverse.Lsh(reverse, 64)
	reverse.Add(reverse, big.NewInt(result[0]))
 
	fmt.Println(reverse.String())
 
	fmt.Println(initial.String() == reverse.String())
}

答案1

得分: 2

这里有几个问题:

value 不能由 int64 表示,所以 value.Int64() 的结果是未定义的。

你没有考虑到 Int64 的有符号结果,所以可能会将一个负数加到结果中。你需要使用 uint64(或者至少在将其添加到 big.Int 之前进行转换)。

你在 Rsh 方法中改变了 value,所以即使值被正确重新创建,最后的比较也会失败。如果你想要比较它,可以创建一个新的 big.Int 来存储原始值。

如果你想要一个精确表示为 128 位的 big.Int 的原始数据表示,你可以使用 FillBytes 方法。我们可以将这个大端数据构建成两个 64 位的值,如下所示:

b := make([]byte, 16)
value.FillBytes(b)	

var result [2]uint64
result[0] = binary.BigEndian.Uint64(b[:8])
result[1] = binary.BigEndian.Uint64(b[8:])

现在字节顺序已经固定,将符号位添加到结果中。为了使其像一个 int128 一样工作,我们需要使用二进制补码来设置符号位:

const sign = uint64(1 << 63)
if value.Sign() < 0 {
	// 将无符号值转换为二进制补码
	result[0] = ^result[0]
	result[1] = ^result[1]

	result[1]++
	// 检查进位
	if result[1] == 0 {
		result[0]++
	}
}

要创建一个新的 big.Int,反转整个过程:

neg := uint128[0]&sign != 0
if neg {
	// 反转二进制补码
	if uint128[1] == 0 {
		uint128[0]--
	}
	uint128[1]--

	uint128[0] = ^uint128[0]
	uint128[1] = ^uint128[1]
}

b := make([]byte, 16)
binary.BigEndian.PutUint64(b[:8], uint128[0])
binary.BigEndian.PutUint64(b[8:], uint128[1])

result := new(big.Int).SetBytes(b)
if neg {
	result.Neg(result)
}

一个测试多个关键值的示例:https://go.dev/play/p/E1E-5CilFlr

因为输出被写为无符号值,如果可能的话,如果要处理的值大于 MaxInt128,你还应该添加一个检查,以确保不会溢出有符号值。将这些存储为 [2]int64 会更加混乱,因为我们需要 uint64 值进行位操作,并且我们需要确保 int64 值不会通过它们自己的二进制补码翻转。在这种情况下,最好在给定的函数周围将 [2]int64 转换为 [2]uint64

英文:

There are a number of problems here:

value cannot be represented by an int64, so the result of value.Int64() is undefined.

Your lower bits are not taking into account the signed result of Int64, so you could be adding a negative number to the result. You need to use a uint64 (or at at least convert it before adding it to the big.Int).

You are mutating value in the Rsh method, so the comparison at the end would fail even if the value were recreated correctly. Create a new big.Int to store the original value if you want to compare it.

If you want a raw data representation for the big.Int with exactly 128bits, you can use the FillBytes method. We can take that big-endian data and build the 2 64bit values like so:

b := make([]byte, 16)
value.FillBytes(b)	

var result [2]uint64
result[0] = binary.BigEndian.Uint64(b[:8])
result[1] = binary.BigEndian.Uint64(b[8:])

Now that the byte order is fixed, add the sign bit to the result. In order to make this work like an int128 however, we need to use two's compliment to set the sign

const sign = uint64(1 &lt;&lt; 63)
if value.Sign() &lt; 0 {
	// convert the unsigned value to two&#39;s compliment
	result[0] = ^result[0]
	result[1] = ^result[1]

	result[1]++
	// check for carry
	if result[1] == 0 {
		result[0]++
	}
}

To create a new big.Int, reverse the entire process:

neg := uint128[0]&amp;sign != 0
if neg {
	// reverse the two&#39;s compliment
	if uint128[1] == 0 {
		uint128[0]--
	}
	uint128[1]--

	uint128[0] = ^uint128[0]
	uint128[1] = ^uint128[1]
}

b := make([]byte, 16)
binary.BigEndian.PutUint64(b[:8], uint128[0])
binary.BigEndian.PutUint64(b[8:], uint128[1])

result := new(big.Int).SetBytes(b)
if neg {
	result.Neg(result)
}

An example testing a number of key values: https://go.dev/play/p/E1E-5CilFlr

Because the output is written as an unsigned value, if it's possible to start with values > MaxInt128, you should also add a check to make sure you're not overflowing the signed value. Storing these as [2]int64 is a lot messier because we need uint64 values for the bitwise operations, and we need to make sure the int64 values aren't rolled over via their own two's compliment. In that case it's easier to convert the [2]int64 to and from [2]uint64 around the given functions.

huangapple
  • 本文由 发表于 2022年12月7日 05:45:36
  • 转载请务必保留本文链接:https://go.coder-hub.com/74709367.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定