最快获得二进制数量 [英] Fastest get count of binary ones in number

问题描述

嗨..

我有问题..

我必须找出这样一个数字，其中等级（顺序）是''N''，但是这个我计算的数字只是二进制代码中有''< = L''的数字..

最大数字可以有31位..


可以帮帮我吗？ （对不起我的英语）



（这一定要这么快..）

解决方案

< blockquote>我真的很喜欢nv3的解决方案。我给了它五颗星。我非常喜欢它，所以我决定试一试并开发一个VB .NET程序来使用nv3的方法来计算位数。我知道你想要一个C或C ++的例子，但VB .NET对我来说更容易。您可以使用免费的源代码翻译器 [ ^ ]将其转换为C＃以接近C或C ++语法。



首先，我写了一个小程序来生成查找表并将值复制到剪贴板，这样我就可以将它们粘贴到我的位计数程序中。

 Dim x As Integer 
 Dim y As Integer 
 Dim z As Integer 
 Dim s As String ={
 For x = 0 to 255 
z = 0 
 Dim b As New BitArray（{x}）
 For y = 0 To 31 
z + = DirectCast（IIf（b（y），1,0），Integer）
下一个
s + = z.ToString& ，
下一个
 s = s.Substring（0，s.Length  -  1）& }
 Clipboard.SetData（DataFormats.Text，s）

然后，我开发了以下程序来做计算。我使用无符号整数，因为对有符号整数的位移操作会传播符号值。 Dim arrValues（）As Integer 设置为我在第一个程序中计算的值的字符串。

 Dim arrValues（）As Integer = {0 ，1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,3,3 ，3,4,3,4,4,5,1,2,3,3,3,3,4,3,3,3,4,3,4,4,5,2,3,3 ，4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,3,3,3,3,3,4,3,3,4,4 ，3,4,4,5,2,3,3,4,3,4,5,5,4,4,5,4,5,5,6,2,3,3,4,3 ，4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6 ，6,7,1,2,3,3,3,3,4,3,3,3,4,3,4,4,5,2,3,3,4,3,4,4 ，5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,5,5,4,4,5,4,5,5,6,6,4,5,4,3,5,5,6,3,3,4,3,4,6,5,3,4,5,4,5,5,6 ，3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3 ，4,4,5,4,5,5,6,3,4,5,5,5,5,6,4,5,5,5,6,6,7,3,4,4,6,4,4,5,5,5,3,4,5,4,5,5,6,5,5,6,5,6,6,7,3,4 ，4,5,4,5,5,6,4,5,5,6,5,6,7,7,5,5,6,5,6,6,7,5,6,6,6,4,6,5,6,6,5,4,6,5,6,6,7,5,5,5,5,6,6,7,5,6,6 ，7,6,7,7,8} 
 Dim intValue As UInteger = 2433815039''这个值中有多少位= 1？ 
 Dim intTemp As UInteger 
 Dim intCountOfBits As Integer = 0 
''
''无符号整数有四组8位（总共32位）
' '8位保持0到255之间的值。
''对于下面的评论，我从左到右编号四组（1-4）
''
 intTemp = intValue >> 24''向右移24位以移除最左边的8位（组1）
 intCountOfBits = arrValues（intTemp）''查找此组8位中的位数（索引= 0-255）
 intTemp = intValue<< 8''向左移8位以移除最左边的8位
 intTemp>> = 24''右移24位以隔离第二组8位
 intCountOfBits + = arrValues（intTemp）''查找此组8位中打开的位数（索引= 0-255）
 intTemp = intValue<< 16''向左移16位以移除最左边的16位
 intTemp>> = 24''向右移24位以隔离第3组8位
 intCountOfBits + = arrValues（intTemp）''查找此组8位中打开的位数（索引= 0-255）
 intTemp = intValue<< 24''向左移24位以移除最左边的24位
 intTemp>> = 24''右移24位以隔离第四组8位
 intCountOfBits + = arrValues（intTemp）''查找此组8位中打开的位数（索引= 0-255）
 MsgBox（intCountOfBits.ToString）

一种可能性是来自John C. Wren： http://www.sjbaker.org/wiki/index.php?title= Cool_Code_list [ ^ ]



代码为：

 n =（n& 0x55555555）+（（n& 0xaaaaaaaa ）>>  1 ）; 
 n =（n& 0x33333333）+（（n& 0xcccccccc）>>  2 ）; 
 n =（n& 0x0f0f0f0f）+（（n& 0xf0f0f0f0）>>  4 ）; 
 n =（n& 0x00ff00ff）+（（n& 0xff00ff00）>>  8 ）; 
 n =（n& 0x0000ffff）+（（n& 0xffff0000）>>  16 ）; 
 

在这里也可以看到类似的问题：



< a href =http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer> http://stackoverflow.com / questions / 109023 /如何计算32位整数中的设置位数[ ^ ]

创建一个查找表，其中包含每个8位值的1位数。然后将该映射应用于32位值中的四个8位组，并添加四位计数。



以下是查找表的外观：< br $>


表[0] = 0

表[1] = 1

表[2] = 1

表[3] = 2

表[4] = 1

表[5] = 2

表[6] = 2

表[7] = 3



...



table [255] = 8



要将32位值拆分为4个8位组，您可以使用移位和掩码方法或定义与数组BYTE的联合并访问其数组成员。

Hi..
I have a problem..
I must find out such a number, which rank (order) is ''N'', but this numbers which i counts is only numbers which in binary code has '' <= L '' ones..
Maximal number can has 31 bits..

Can help me? (I''m sorry for my English )

(this must be so fast..)

解决方案

I really liked nv3''s Solution. I gave it five stars. I liked it so much that I decided to try it out and develop a VB .NET program to count bits using nv3''s method. I know you wanted an example in C or C++ but VB .NET is easier for me. You could use one of the free source code translators[^] to convert it to C# to get closer to C or C++ syntax.

First, I wrote a small program to generate the lookup table and copy the values to the clipboard so I could paste them into my bit count program.

Dim x As Integer
Dim y As Integer
Dim z As Integer
Dim s As String = "{"
For x = 0 To 255
     z = 0
     Dim b As New BitArray({x})
     For y = 0 To 31
        z += DirectCast(IIf(b(y), 1, 0), Integer)
     Next
     s += z.ToString & ","
Next
s = s.Substring(0, s.Length - 1) & "}"
Clipboard.SetData(DataFormats.Text, s)

Then, I developed the following program to do the computation. I used Unsigned Integer because bit shift operations on Signed Integers propagate the sign value. The Dim arrValues() As Integer is set to the string of values that I computed in my first program.

Dim arrValues() As Integer = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}
Dim intValue As UInteger = 2433815039 '' How many bits=1 in this value?
Dim intTemp As UInteger
Dim intCountOfBits As Integer = 0 
''
'' An unsigned integer has four groups of 8 bits (Total of 32 bits)
'' 8 Bits holds values ranging from 0 to 255.
'' For the comments below, I have numbered the four groups (1-4) from left to right
''
intTemp = intValue >> 24 '' Shift right 24 bits to remove leftmost 8 bits (Group 1)
intCountOfBits = arrValues(intTemp) '' Lookup number of bits that are on in this group of 8 bits (index=0-255)
intTemp = intValue << 8 '' Shift left 8 bits to remove leftmost 8 bits
intTemp >>= 24 '' Shift right 24 bits to isolate second group of 8 bits
intCountOfBits += arrValues(intTemp) '' Lookup number of bits that are on in this group of 8 bits (index=0-255)
intTemp = intValue << 16 '' Shift left 16 bits to remove leftmost 16 bits
intTemp >>= 24 '' Shift right 24 bits to isolate third group of 8 bits
intCountOfBits += arrValues(intTemp) '' Lookup number of bits that are on in this group of 8 bits (index=0-255)
intTemp = intValue << 24 '' Shift left 24 bits to remove leftmost 24 bits
intTemp >>= 24 '' Shift right 24 bits to isolate fourth group of 8 bits
intCountOfBits += arrValues(intTemp) '' Lookup number of bits that are on in this group of 8 bits (index=0-255)
MsgBox(intCountOfBits.ToString)

One possibility is from John C. Wren: http://www.sjbaker.org/wiki/index.php?title=Cool_Code_list[^]

The code is:

n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

See also similar question here:

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer[^]

Make a lookup table that contains for each 8-bit value the number of 1 bits. Then apply that mapping to the four 8-bit groups in your 32-bit value and add the four bit counts.

Here is what the lookup table looks like:

table[0] = 0
table[1] = 1
table[2] = 1
table[3] = 2
table[4] = 1
table[5] = 2
table[6] = 2
table[7] = 3

...

table[255] = 8

To split the 32-bit value into four 8-bit groups you can either use the shift and mask approach or define a union with an array BYTE and access its array members.

这篇关于最快获得二进制数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！