比较两个数组中的比特
问题描述:
我在这本书中遇到了ex4.1:
编写一个函数,用于计算两个SHA256哈希中不同的比特数。比较两个数组中的比特
我想到的部分解决方案粘贴在下面,但它是错误的 - 它计算不同字节的数量而不是位数。 请你指点我正确的方向?
package main
import (
"crypto/sha256"
"fmt"
)
var s1 string = "unodostresquatro"
var s2 string = "UNODOSTRESQUATRO"
var h1 = sha256.Sum256([]byte(s1))
var h2 = sha256.Sum256([]byte(s2))
func main() {
fmt.Printf("s1: %s h1: %X h1 type: %T\n", s1, h1, h1)
fmt.Printf("s2: %s h2: %X h2 type: %T\n", s2, h2, h2)
fmt.Printf("Number of different bits: %d\n", 8 * DifferentBits(h1, h2))
}
func DifferentBits(c1 [32]uint8, c2 [32]uint8) int {
var counter int
for x := range c1 {
if c1[x] != c2[x] {
counter += 1
}
}
return counter
}
答
艾伦AA多诺万·布赖恩W.Kernighan
练习4.1:写functi根据这个数字计算出 在两个SHA256哈希值中不同的位数。
布莱恩·W.Kernighan丹尼斯M. Ritchie的
练习2-9。在二进制补码系统中,
x &= (x-1)
删除x
中最右边的1位。使用这个观察来编写更快的 版本的bitcount
。
肖恩·安德森玉龙
Counting bits set, Brian Kernighan's way
unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set }
对于练习4.1,您正在计算不同的字节的数量。计数位的数目是不同的。例如,
package main
import (
"crypto/sha256"
"fmt"
)
func BitsDifference(h1, h2 *[sha256.Size]byte) int {
n := 0
for i := range h1 {
for b := h1[i]^h2[i]; b != 0; b &= b - 1 {
n++
}
}
return n
}
func main() {
s1 := "unodostresquatro"
s2 := "UNODOSTRESQUATRO"
h1 := sha256.Sum256([]byte(s1))
h2 := sha256.Sum256([]byte(s2))
fmt.Println(BitsDifference(&h1, &h2))
}
输出:
139
答
这里是我会怎么做
package main
import (
"crypto/sha256"
"fmt"
)
var (
s1 string = "unodostresquatro"
s2 string = "UNODOSTRESQUATRO"
h1 = sha256.Sum256([]byte(s1))
h2 = sha256.Sum256([]byte(s2))
)
func main() {
fmt.Printf("s1: %s h1: %X h1 type: %T\n", s1, h1, h1)
fmt.Printf("s2: %s h2: %X h2 type: %T\n", s2, h2, h2)
fmt.Printf("Number of different bits: %d\n", DifferentBits(h1, h2))
}
// bitCount counts the number of bits set in x
func bitCount(x uint8) int {
count := 0
for x != 0 {
x &= x - 1
count++
}
return count
}
func DifferentBits(c1 [32]uint8, c2 [32]uint8) int {
var counter int
for x := range c1 {
counter += bitCount(c1[x]^c2[x])
}
return counter
}
你已经在位元数:8 *的字节数。在Go(或任何其他非嵌入式语言)中逐字阅读是非常非常奇怪的。你确定这本书(哪本书?)希望你这样做?否则,看到这个现有的答案:http://*.com/questions/29583024/reading-8-bits-from-a-reader-in-golang - 但我可以诚实地说,你应该从来没有这样做时,比较哈希在一个真正的节目。 – elithrar
你正在执行的是Hamming Distance,它是一个非常常用和有用的算法。您应该阅读关于字节的按位操作,并且解决方案并不困难 - 异或两个字节以获取仅设置了不同位的字节。然后对比特进行移位计数。 –
@peterSO我不怀疑OP:但是,可能有围绕他们的帖子中没有提供的问题的上下文。如果本书确实希望你进行按位操作,那么在投掷你之前,以前的练习或章节是否会提供一些介绍? (甚至不清楚正在讨论哪本书;我认为它是GoPL)。 – elithrar