Source file src/github.com/bits-and-blooms/bitset/popcnt.go

Documentation: github.com/bits-and-blooms/bitset

     1  package bitset
     2  
     3  // bit population count, take from
     4  // https://code.google.com/p/go/issues/detail?id=4988#c11
     5  // credit: https://code.google.com/u/arnehormann/
     6  func popcount(x uint64) (n uint64) {
     7  	x -= (x >> 1) & 0x5555555555555555
     8  	x = (x>>2)&0x3333333333333333 + x&0x3333333333333333
     9  	x += x >> 4
    10  	x &= 0x0f0f0f0f0f0f0f0f
    11  	x *= 0x0101010101010101
    12  	return x >> 56
    13  }
    14  
    15  func popcntSliceGo(s []uint64) uint64 {
    16  	cnt := uint64(0)
    17  	for _, x := range s {
    18  		cnt += popcount(x)
    19  	}
    20  	return cnt
    21  }
    22  
    23  func popcntMaskSliceGo(s, m []uint64) uint64 {
    24  	cnt := uint64(0)
    25  	for i := range s {
    26  		cnt += popcount(s[i] &^ m[i])
    27  	}
    28  	return cnt
    29  }
    30  
    31  func popcntAndSliceGo(s, m []uint64) uint64 {
    32  	cnt := uint64(0)
    33  	for i := range s {
    34  		cnt += popcount(s[i] & m[i])
    35  	}
    36  	return cnt
    37  }
    38  
    39  func popcntOrSliceGo(s, m []uint64) uint64 {
    40  	cnt := uint64(0)
    41  	for i := range s {
    42  		cnt += popcount(s[i] | m[i])
    43  	}
    44  	return cnt
    45  }
    46  
    47  func popcntXorSliceGo(s, m []uint64) uint64 {
    48  	cnt := uint64(0)
    49  	for i := range s {
    50  		cnt += popcount(s[i] ^ m[i])
    51  	}
    52  	return cnt
    53  }
    54  

View as plain text