13,249,035 members (48,462 online)
Rate this:
See more:
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..)
Posted 28-Feb-13 2:58am
Updated 28-Feb-13 3:01am
Mike Meinz26.8K
v3
Mike Meinz 28-Feb-13 8:02am

Please show an example with real numbers.
phil.o 28-Feb-13 8:04am

Reported as unclear or incomplete.
If you're not fluent in english, please try to write your question in your native language and use an online translator to translate it.
And please post some relevant example also.

Rate this:

## Solution 2

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)```
v4
nv3 28-Feb-13 11:02am

Thanks Mike for the nice demonstration.
Rate this:

## Solution 4

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);
```

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer[^]
v2
nv3 1-Mar-13 7:44am

That is a very elegant approach! Although it might be slightly slower than the lookup table approach, the principal is very interesting. I've learned something new. Thanks for sharing it, Philippe.

5ed.
—SA
Rate this:

## Solution 1

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.
v2

Top Experts
Last 24hrsThis month
 phil.o 90 ppolymorphe 75 Bryian Tan 50 Ralf Meier 35 Member 12895537 35
 OriginalGriff 3,414 Karthik Bangalore 1,992 ppolymorphe 1,399 Dave Kreskowiak 1,276 CPallini 1,215