2016-01-23 176 views
2

我在这本书中遇到了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 

} 
+0

你已经在位元数:8 *的字节数。在Go(或任何其他非嵌入式语言)中逐字阅读是非常非常奇怪的。你确定这本书(哪本书?)希望你这样做?否则,看到这个现有的答案:http://stackoverflow.com/questions/29583024/reading-8-bits-from-a-reader-in-golang - 但我可以诚实地说,你应该从来没有这样做时,比较哈希在一个真正的节目。 – elithrar

+1

你正在执行的是Hamming Distance,它是一个非常常用和有用的算法。您应该阅读关于字节的按位操作,并且解决方案并不困难 - 异或两个字节以获取仅设置了不同位的字节。然后对比特进行移位计数。 –

+0

@peterSO我不怀疑OP:但是,可能有围绕他们的帖子中没有提供的问题的上下文。如果本书确实希望你进行按位操作,那么在投掷你之前,以前的练习或章节是否会提供一些介绍? (甚至不清楚正在讨论哪本书;我认为它是GoPL)。 – elithrar

回答

2

The Go Programming Language

艾伦AA多诺万·布赖恩W.Kernighan

练习4.1:写functi根据这个数字计算出 在两个SHA256哈希值中不同的位数。


The C Programming Language

布莱恩·W.Kernighan丹尼斯M. Ritchie的

练习2-9。在二进制补码系统中,x &= (x-1)删除 x中最右边的1位。使用这个观察来编写更快的 版本的bitcount


Bit Twiddling Hacks

肖恩·安德森玉龙

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 
1

这里是我会怎么做

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 
} 

Playground