0

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?

1

4 Answers 4

3

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];
3

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])
}
1

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.

1

there is POPCNT golang version:

https://github.com/tmthrgd/go-popcount

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.