求二进制中1的个数

type(value) == uint64

• 循环求解
  核心：判断value最低位是否为1，循环右移1位，直到value==0
  时间复杂度：最高1bit出现的位置
  空间复杂度：O(1)

func coutBits(value uint64) int {
    var count int
    for ; value != 0; value>>=1 {
        count += int(value & 1)
    }
    return count
}

• bit位求解
  核心：value&(value-1)把最低位非0位置0；循环；直到value==0
  时间复杂度：value中1bit出现的个数
  空间复杂度：O(1)

func coutBits(value uint64) int {
    var count int
    for ; value!=0; value=value&(value-1) {
        count += 1
    }
    return count
}

• • 如果事先确定1bit位数目多余0bit位的数目，可以有以下优化方法。
    核心：value值，0变1，1变0；再采用上述算法计算1bit数目(即原值0bit数目)；64-count即为要求的值

func coutBits(value uint64) int {
    var count int
    value ^= uint64(1<<64-1)
    for ; value!=0; value=value&(value-1) {
        count += 1
    }
    return 64-count
}

• 查表求解
  核心：

• 预先计算、生成8bit数字，每一个对应的1bit数目；value循环右移8bit；查表累计求和
• i << 1 == i*2, bitCountMap[2*i] = bitCountMap[i] + (2*i)&1
  时间复杂度：8
  空间复杂度：256

var bitCountMap map[uint]uint
func init() {
    bitCountMap = make(map[uint]uint)
    for i:=uint(0); i<256; i++ {
        bitCountMap[i] = bitCountMap[i/2] + i&1
    }
}
func coutBits(value uint64) uint {
    var count uint
    for ; value!=0; value>>=8 {
        count += bitCountMap[uint(value&0xff)]
    }
    return count
}

这是8bit查找表，当然也可以16bit查找表