英文:
How count how many one bit have in byte, in Golang?
问题
假设我有两个只使用6位的变量：
var a byte = 31 // 00011111
var b byte = 50 // 00110010
第一个变量（a）比变量b有更多的位为1，然而显然b大于a，所以不可能使用a > b。
为了实现我需要的功能，我使用了一个循环：
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
}
这个方法有效，我可以使用countOneBits(a) > countOneBits(b)...
但是我不认为这是这种情况下的最佳解决方案，我认为这不需要循环，因此我在这里。
有没有更好的替代方案（从性能方面）来计算六位中有多少个1？
英文:
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
得分: 3
考虑到输入是一个单字节，最好的选择可能是使用查找表...只需要256个字节，你就可以得到如下的代码：
var count = bitcount[input];
英文:
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];
答案2
得分: 3
给定这个函数将在下一个Go版本（8月份的1.9版本）的包math/bits中可用，这是一个32位整数的代码示例。
// OnesCount32 返回 x 中的一位比特数（"population count"）。
func OnesCount32(x uint32) int {
return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
}
其中 pop8tab 在这里被定义。对于你的问题，特别是8位的情况：
func OnesCount8(x uint8) int {
return int(pop8tab[x])
}
英文:
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])
}
答案3
得分: 1
也可以使用二进制操作来计算位数。请参考这个位操作技巧。
func bitSetCount(v byte) byte {
v = (v & 0x55) + ((v>>1) & 0x55)
v = (v & 0x33) + ((v>>2) & 0x33)
return (v + (v>>4)) & 0xF
}
你需要进行基准测试来确定这种方法是否比查找表更快，查找表是最简单实现的方法。
英文:
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.
答案4
得分: 1
这是POPCNT的Go语言版本：
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论