2016-01-23 175 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