Hello,

    What's the fastest way to count the number of 'ON' bits in a given
'long' value? I ask this bizzare question because I'm writing a little
utility that deals with IP addresses and subnet masks. For example, if I
have:

    unsigned long lSubnetMask=0xfffffff0;
    char cBitCount=countTheBits(lSubnetMask);
    assert(cBitCount==28);

    How would I implement countTheBits()?

    The only way that I can think of to approach this problem is to enter a
loop, ANDing lSubnetMask by: 0x01,0x02,0x04,0x08...0x80000000 and simply
count the number of times that the AND operation returns non-zero. That's a
lot of loop iterations, though. Is there a faster way?

--
David Sworder
Software Development

Not really, though your approach is a bit long winded.  The fastest solution
would probably be

int count = 0;
unsigned long lSubnetMask=0xfffffff0;

for (int i=0; i < 32; i++) {
    count += lSubnetMask & (1 <<  i);  // shifts bit i number of times

I'm not sure why you want to know the number of bits in subnet mask though,
since the mask's pertinent information is defined by it's position, not by
how many of them there are.

The coding can be made minimal:

        unsigned i, bitcount = 0;
        for (i=0; i<32; i++) if (bitfield & ((0x00000001)<<i)) bitcount++;

As for fast ... I don't know ... thirty-two "if"s written in assembly with
hard-coded constants for comparison would probably be pretty fast.

 - Vince

Vincent Fatica

Syracuse University Mathematics
http://barnyard.syr.edu/~vefatica/

    The reason that I want to count the bits is that a network ID/subnet
mask is sometimes expressed using the following notation:

192.168.111.0/24

    That is the equivalent of saying, "I have a network ID of 192.168.111.0
with a subnet mask of 255.255.255.0"... The 24 represents the 24 bits that
are set to ON in the subnet mask.... or at least that is how it was
explained to me.

David

Ummm.. no.  since the entire 255.255.255.255 subnet is one 32 bit value, 24
bits would be 3/4 of them, in other words 255.0.0.0

Besides, remember that bitmasks are not evenly distributed.  the bit patter
could look like this:  1010101010101010.  This would count 8 bits, but
clearly it's not equal to 00000000111111111.

I suggest you do some research on bitmasks before writing code to manipulate
them.

Yes, probably.  One that's been around a while is:

#define BX_(x)          ((x) - (((x)>>1)&0x77777777)            \
                             - (((x)>>2)&0x33333333)            \
                             - (((x)>>3)&0x11111111))

#define BITCOUNT(x)     (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)

One way that CAN be a little faster is a lookup table: basically
something like:

table[x & 0xff] + table[(x>>8) & 0xff] + table[(x>>16) & 0xff] +
table[(x>>24) & 0xff];

Obviously you then have to build a table of how many bits are set in
each possible 8-bit value:

char table[255] = {
        0,
        1,
        1,
        2,
        1,
        2,
        2,
        3,

        // ...

        7,
        8

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

Go to http://www.snippets.org and look at:

Bit-level operations
=====================
File         O/S  Description
------------ ---  -------------------
Bitops.H     any  Prototypes, plus macros to set, clear, and test bits
Bitops.How   any  How the BitXxx() macros in BITOPS.H work
Bitarray.C   any  Bit array functions
Bitcnt_1.C   any  Count bits in a number (fast, clever)
Bitcnt_2.C   any  Count bits in a number (fascinating)
Bitcnt_3.C   any  Count bits in a number (table look-up)
Bitcnt_4.C   any  Count bits in a number (recursive table look-up)
Bitcnts.C    any  Benchmark to test BITCNT_x.C functions
Bitfiles.C   any  Read/write bit files
Bitstrng.C   any  Print binary formatted strings
Bstr_I.C     any  Convert binary string to int

--
Wayne A. King

The standard way to speed up an algorithm is to use memory to keep
precalculated data.

unsigned char t[256];
void init (void) {
    for (int j = 0; j < 256; j++) {
 t[j] = 0;
 for (int i=0; i < 8; i++)
     t[j] += (j >> i) & 1;
    }

int countTheBits (unsigned long l) {
    return t[l&0xff] + t[(l>>8) & 0xff] + t[(l >> 16) & 0xff] + t[l>>24];

  init();    // precalculate the t array
  cout << countTheBits (0xff) << ", " << countTheBits (0xffff) << ", " <<
countTheBits (0xffffffff) << endl;

: Hello,

:     What's the fastest way to count the number of 'ON' bits in a given
: 'long' value? I ask this bizzare question because I'm writing a little
: utility that deals with IP addresses and subnet masks. For example, if I
: have:

:     unsigned long lSubnetMask=0xfffffff0;
:     char cBitCount=countTheBits(lSubnetMask);
:     assert(cBitCount==28);

:     How would I implement countTheBits()?

:     The only way that I can think of to approach this problem is to enter a
: loop, ANDing lSubnetMask by: 0x01,0x02,0x04,0x08...0x80000000 and simply
: count the number of times that the AND operation returns non-zero. That's a
: lot of loop iterations, though. Is there a faster way?

I'll assume here that unsigned longs have 32 bits; really you should
probably use a type that is guaranteed to be this size.

There is a general way to do this:

/* lSubnetMask contains 32 1-bit counters to be summed */
unsigned long count = (lSubnetMask & 0x55555555)
                    + ((lSubnetMask & 0xAAAAAAAA) >> 1);
/* count contains 16 2-bit counters to be summed */
count = (count & 0x33333333) + ((count & 0xCCCCCCCC) >> 2);
/* count contains 8 4-bit counters to be summed */
count = (count & 0x0F0F0F0F) + ((count & 0xF0F0F0F0) >> 4);
/* count contains 4 8-bit counters to be summed */
count = (count & 0x00FF00FF) + ((count & 0xFF00FF00) >> 8);
/* count contains 2 16-bit counters to be summed */
count = (count & 0x0000FFFF) + ((count & 0xFFFF0000) >> 16);

10 shifts, 10 masks, 5 additions.

Your problem is more specific, in that all the 1-bits are to the left,
but I can't see any obvious optimisations based on that.  You could do
something like this:

unsigned long temp = lSubnetMask;
int count = 32;
if( (temp & 0xFFFF) == 0 )
    {count = 16; temp >>= 16;}
if( (temp & 0xFF) == 0 )
    {count -= 8; temp >>= 8;}
if( (temp & 0xF) == 0 )
    {count -= 4; temp >>= 4;}
if( (temp & 3) == 0 )
    {count -= 2; temp >>= 2;}
if( (temp & 1) == 0 )
{
    count -= 1; temp >>= 1;
    if( (temp & 1) == 0 )
        count -= 1;

but I doubt that it's faster - conditional branches can be slow.

--
Any opinions expressed are my own and not necessarily those of Laser-Scan.

I think it was explained incorrectly.  The 24 represents a subnet mask
with the high-order 24 bits on, regardless of the network ID.  That value
is much easier to compute:

        (0xFFFFFFFFlu << (32 - n)) & 0xFFFFFFFlu

where n (0 <= n < 32) is the number after the /.  I believe that this
expression is portable to all implementations of C and C++ because it
forces the computation into long unsigned, which is required to be at
least 32 bits.  The "& 0xFFFFFFFFlu" is unnecessary on an implementation
on which long unsigned is exactly 32 bits.
--

There is one thing puzzling me while reading this thread:
Why would the OP want to ***count*** the number of bits.
If I understood the later explanation correctly, he already
has the number of bits (eg.24) and wants to generate
the mask for this number.
Your solution does exactly this.

But the question remains on my side:
Why would you want to count the number of bits?
Especially when taking into account that 255.255.255.2
is a perfectly valid network mask, which cannot be expressed
by just giving the number of 1-bits.

-----------------------------------------------------------
Karl Heinz Buchegger

Whoops!
I think I meant:

for(count = (value != 0); value; value &= value - 1)
    count++;

(so count is always starts as 1 in the loop when the value is non-zero!)

(and, no I didn't get that one by myself, other than to compress
it horribly all into one single statement).

It works by clearing the right-most bit in value (which ever bit that might
be), and
only executes for *the number of bits that exist in value*

James

--
Please remove "NOSPAM" from the front of my mail address.

    I would want to count the number of bits if I had access to an network
ID and subnet mask (both stored as a ULONGs), and wanted to convert these
ULONGS to a single text string such as:

"192.168.112.0/24"

    In order to do this, I need to count the number of bits in the ULONG
subnet mask in order to generate the "24".

    This is news to me. I didn't realize that you could have a subnet mask
like 255.255.255.2...I thought that a subnet mask was ALWAYS a continuous
stream of 1's followed by a continuous stream of 0's. It appears that the
router we are using doesn't allow for such masks, however, as it forces us
to use the "bit count" string notation listed above.

<snip>
: Your problem is more specific, in that all the 1-bits are to the left,
: but I can't see any obvious optimisations based on that.  You could do
: something like this:
<snip>
: but I doubt that it's faster - conditional branches can be slow.

But, having coincidentally been presented with a similar problem, I
now realise that you can do a lot better with a lookup table, as
suggested by another poster.

--
Any opinions expressed are my own and not necessarily those of Laser-Scan.

If all the one bits are to the left, you could use:

int temp = value; // use a signed value

for (bitcount = 0; temp < 0; temp <<= 1, ++bitcount);