in information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

also called the population count, popcount, sideways sum, or bit summation.

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used.

``````# Golang 中的实现 math/bits/make_table.go #popcount

func pop8(x uint8) (n uint8) {
for x != 0 {
x &= x - 1
n++
}
return
}

# 具体实现中，预生成了1 byte uint8的ones string，通过索引快速查到1的数量

// OnesCount8 returns the number of one bits ("population count") in x.
func OnesCount8(x uint8) int {
return int(pop8tab[x])
}

// OnesCount16 returns the number of one bits ("population count") in x.
func OnesCount16(x uint16) int {
return int(pop8tab[x>>8] + pop8tab[x&0xff])
}

// OnesCount32 returns the number of one bits ("population count") in x.
func OnesCount32(x uint32) int {
return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
}

// OnesCount64 returns the number of one bits ("population count") in x.
func OnesCount64(x uint64) int {
// Implementation: Parallel summing of adjacent bits.
// See "Hacker's Delight", Chap. 5: Counting Bits.
// The following pattern shows the general approach:
//
//   x = x>>1&(m0&m) + x&(m0&m)
//   x = x>>2&(m1&m) + x&(m1&m)
//   x = x>>4&(m2&m) + x&(m2&m)
//   x = x>>8&(m3&m) + x&(m3&m)
//   x = x>>16&(m4&m) + x&(m4&m)
//   x = x>>32&(m5&m) + x&(m5&m)
//   return int(x)
//
// Masking (& operations) can be left away when there's no
// danger that a field's sum will carry over into the next
// field: Since the result cannot be > 64, 8 bits is enough
// and we can ignore the masks for the shifts by 8 and up.
// Per "Hacker's Delight", the first line can be simplified
// more, but it saves at best one instruction, so we leave
// it alone for clarity.
const m = 1<<64 - 1
x = x>>1&(m0&m) + x&(m0&m)
x = x>>2&(m1&m) + x&(m1&m)
x = (x>>4 + x) & (m2 & m)
x += x >> 8
x += x >> 16
x += x >> 32
return int(x) & (1<<7 - 1)
}
``````