Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ C
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
Edited 28-Feb-13 2:01am
Mike Meinz20.8K
v3
Comments
Mike Meinz at 28-Feb-13 8:02am
   
Please show an example with real numbers.
phil.o at 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: bad
good
Please Sign up or sign in to vote.

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)
  Permalink  
v4
Comments
nv3 at 28-Feb-13 11:02am
   
Thanks Mike for the nice demonstration.
Rate this: bad
good
Please Sign up or sign in to vote.

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);
 
See also similar question here:
 
http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer[^]
  Permalink  
v2
Comments
nv3 at 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 at 25-Mar-13 1:10am
   
5ed.
—SA
Rate this: bad
good
Please Sign up or sign in to vote.

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

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

  Print Answers RSS
0 OriginalGriff 259
1 Sergey Alexandrovich Kryukov 182
2 Hard_Rockz 153
3 Richard MacCutchan 125
4 Maciej Los 104
0 OriginalGriff 5,374
1 Sergey Alexandrovich Kryukov 4,713
2 Peter Leow 2,944
3 DamithSL 2,465
4 Maciej Los 2,270


Advertise | Privacy | Mobile
Web03 | 2.8.140718.1 | Last Updated 28 Feb 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid