Golang中如何实现big.Int数值的奇偶转换

Golang中如何实现big.Int数值的奇偶转换 我的代码生成了一个如下的 big.Int 数字：

package main

import (
	"fmt"
	"crypto/sha256"
	"math/big"
	"golang.org/x/crypto/blake2b"
)

func main() {
	test := "hello"
	h := sha256.New()
	s := fmt.Sprintf("%v", test)
	sum := h.Sum([]byte(s))
	hash := blake2b.Sum256(sum)
	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Println(zz)
}

我需要将 zz 的值加一。有人能建议最高效的方法吗？我认为最高效的方式是对 zz 的最低有效位进行异或操作，但我不确定在 Go 中如何实现。 谢谢


更多关于Golang中如何实现big.Int数值的奇偶转换的实战教程也可以访问 https://www.itying.com/category-94-b0.html

11 回复

MethodA 运行完美，谢谢！

更多关于Golang中如何实现big.Int数值的奇偶转换的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


这个算法（b = not(a); b = neg(b)）用于递增一个数字，其优雅程度令人印象深刻。

XOR 最低有效位 [以加 1]

这将使偶数增加，使奇数减少。

我的问题表述有误。我不需要将一个大数加一，只需要让它变成偶数（如果它是奇数），反之亦然。

感谢大家的回复。我的目标确实是将一个偶数变为奇数（所以如果将其减一也是可以的）。我会尝试你们的建议，并带着我的发现回来。

为什么 shasum 是一个字符串？该算法本意是操作由 blake2b.Sum256() 返回的字节切片/数组。

我对它的速度如此之慢感到有些惊讶。也许，展开一次循环可能会加快速度。

此外，你正在执行 ToLower()，这会遍历每个字符并分配字符串的副本。这正是消耗 CPU 的原因。

NobbZ: 这将会使偶数递增，使奇数递减。

Christophe_Meessen: 这个用于递增数字的算法（b = not(a); b = neg(b)）优雅得令人印象深刻。

哈哈，谢谢。可惜性能提升不大。我还在探索其他逻辑门，看看还能想出什么。

目前，我正忙于一项密码学研究工作。😅

yewebi:

我的问题表述有误。我并不是需要将一个大数加一，只是需要让它变成偶数（如果它是奇数的话），反之亦然。

你可能需要重新命名这个主题（前缀：已重命名 - …）。目前所有的方法都没有涉及奇偶数的掩码操作，而这才是你的真实意图。给我一些时间来研究一下。

也许直接使用字节操作比使用大整数（bigInt）更快。 使用 not 和 neg 的问题在于它们需要修改所有字节。而递增操作可能只需要修改几个字节。不确定原帖作者为什么需要大整数。

以下是对字节切片应用递增操作的代码：

i := len(hash)-1
for i >= 0 {
    hash[i]++
    if hash[i] != 0 {
        break
    }
    i--
}
if i < 0 {
    // 溢出
}
// 如果需要，将结果哈希值赋值给一个大整数。

递增操作导致溢出的可能性非常小，因为只有当初始数字的所有位都是1时才会发生。

我认为最高效的方式是对 zz 的最低位进行异或操作。

我使用非门和二进制补码的方法实现了一个（命名为 methodA）。methodB 是标准的加 1 方法。

package main

import (
	"fmt"
	"math/big"
)

func methodB(x *big.Int) {
	x.Add(x, big.NewInt(1))
}

func methodA(x *big.Int) {
	x.Not(x)
	x.Neg(x)
}

func main() {
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method A: %s\n", zz.String())
	methodA(zz)
	fmt.Printf("AFTER method A : %s\n", zz.String())

	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method B: %s\n", zz.String())
	methodB(zz)
	fmt.Printf("AFTER method B : %s\n", zz.String())
}
// Output:
// BEFORE method A: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method A : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865
// BEFORE method B: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method B : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865

在我的本地系统上对两者进行基准测试，结果如下：

goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkMethodA-8      25956531                44.1 ns/op
BenchmarkMethodB-8      17653945                65.8 ns/op
PASS
ok      gosandbox       2.425s
基准测试代码 
package main

import (
	"math/big"
	"testing"
)

func BenchmarkMethodA(b *testing.B) {
	tgt := new(big.Int)
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	for i := 0; i < b.N; i++ {
		tgt.SetBytes(hash[:])
		methodA(tgt)
	}
}

func BenchmarkMethodB(b *testing.B) {
	tgt := new(big.Int)
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	for i := 0; i < b.N; i++ {
		tgt.SetBytes(hash[:])
		methodB(tgt)
	}
}

与 methodB 相比，在可读性方面并没有获得多少好处。

有人能建议如何最高效地实现这个吗？

你可能需要在你的系统上运行基准测试来比较所有的提议方案。

在Go中，对big.Int进行奇偶转换（加1操作）最高效的方法是使用Add方法。虽然你提到了异或操作，但对于大整数加1来说，直接使用内置的加法操作更清晰且性能良好。

以下是两种实现方式：

方法1：使用Add方法（推荐）

package main

import (
	"fmt"
	"crypto/sha256"
	"math/big"
	"golang.org/x/crypto/blake2b"
)

func main() {
	test := "hello"
	h := sha256.New()
	s := fmt.Sprintf("%v", test)
	sum := h.Sum([]byte(s))
	hash := blake2b.Sum256(sum)
	
	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Println("原始值:", zz)
	
	// 加1操作
	one := big.NewInt(1)
	zz.Add(zz, one)
	fmt.Println("加1后:", zz)
}

方法2：使用异或操作（按你的思路）

如果你确实想通过操作最低有效位来实现加1，可以这样做：

package main

import (
	"fmt"
	"crypto/sha256"
	"math/big"
	"golang.org/x/crypto/blake2b"
)

func addOneByXOR(z *big.Int) *big.Int {
	result := new(big.Int).Set(z)
	one := big.NewInt(1)
	
	// 使用异或和进位处理
	carry := big.NewInt(1)
	for carry.Sign() != 0 {
		// 计算当前位加carry的结果
		sum := new(big.Int).Xor(result, carry)
		carry.And(result, carry)
		carry.Lsh(carry, 1)
		result.Set(sum)
	}
	
	return result
}

func main() {
	test := "hello"
	h := sha256.New()
	s := fmt.Sprintf("%v", test)
	sum := h.Sum([]byte(s))
	hash := blake2b.Sum256(sum)
	
	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Println("原始值:", zz)
	
	// 使用异或方法加1
	zz = addOneByXOR(zz)
	fmt.Println("加1后:", zz)
}

性能对比

实际上，对于big.Int类型，内置的Add方法已经经过高度优化，通常比手动实现的异或操作更高效。big.Int的加法实现会处理各种边界情况和性能优化：

// 内置Add方法的简化示意
func (z *big.Int) Add(x, y *big.Int) *big.Int {
	// Go运行时会有针对大整数的优化实现
	// 包括处理不同符号、长度等情况
}

验证结果

你可以验证两种方法得到相同的结果：

package main

import (
	"fmt"
	"crypto/sha256"
	"math/big"
	"golang.org/x/crypto/blake2b"
)

func main() {
	test := "hello"
	h := sha256.New()
	s := fmt.Sprintf("%v", test)
	sum := h.Sum([]byte(s))
	hash := blake2b.Sum256(sum)
	
	zz1 := new(big.Int)
	zz1.SetBytes(hash[:])
	zz2 := new(big.Int).Set(zz1)
	
	// 方法1：使用Add
	one := big.NewInt(1)
	zz1.Add(zz1, one)
	
	// 方法2：使用异或
	zz2 = zz2.Add(zz2, one)
	
	fmt.Println("Add方法结果:", zz1)
	fmt.Println("直接加1结果:", zz2)
	fmt.Println("结果相等:", zz1.Cmp(zz2) == 0)
}

在实际使用中，直接使用zz.Add(zz, big.NewInt(1))是最简洁高效的方式。big.Int的Add方法会原地修改接收者，避免了额外的内存分配，这对于大整数操作是很重要的性能优化。

回到顶部