Suppose I have two variables, that only use 6 bits:
var a byte = 31 // 00011111
var b byte = 50 // 00110010
The first (a) have more one bits than the b, however the b is greater than a of course, so is not possible use a > b.
To achieve what I need, I do one loop:
func countOneBits(byt byte) int {
var counter int
var divider byte
for divider = 32; divider >= 1; divider >>= 1 {
if byt & divider == divider {
counter++
}
}
return counter
}
This works, I can use countOneBits(a) > countOneBits(b)...
But I don't think is the best solution for this case, I don't think this need a loop and because of it I'm here.
Have a better alternative (in performance aspect) to count how many 1 have in six bits?
Given that the input is a single byte probably a lookup table is the best option... only takes 256 bytes and you get code like
var count = bitcount[input];
Given that this function will be available in the packagemath/bits in the next Go release (1.9 this August) here is the code for a 32-bit integer.
// 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])
}
Where the pop8tab is defined here. And for your question in particular : 8bits
func OnesCount8(x uint8) int {
return int(pop8tab[x])
}
It is also possible to count bits with binary operations. See this bit twiddling hacks.
func bitSetCount(v byte) byte {
v = (v & 0x55) + ((v>>1) & 0x55)
v = (v & 0x33) + ((v>>2) & 0x33)
return (v + (v>>4)) & 0xF
}
You'll have to benchmark to see if this is faster than the lookup table which is the simplest to implement.
there is POPCNT golang version: