Fastest get count of binary ones in number

Question

1.00/5 (1 vote)

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 1:58am

matko693

Updated 28-Feb-13 2:01am

Mike Meinz

v3

Add a Solution

Comments

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.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Mike Meinz · Answer 1 · 2013-02-28T04:53:00

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)

Philippe Mori · Answer 2 · 2013-02-28T17:10:00

Solution 4

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

The code is:

C++

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[^]

Posted 28-Feb-13 17:10pm

Philippe Mori

Updated 28-Feb-13 17:20pm

v2

Comments

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.

Sergey Alexandrovich Kryukov 25-Mar-13 1:10am

5ed.
—SA

nv3 · Answer 3 · 2013-02-28T02:28:00

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.

Fastest get count of binary ones in number

3 solutions

Solution 2

Solution 4

Solution 1

Add your solution here

Preview 0