Bits Counting (using & and | operators)
Author Message
Bits Counting (using & and | operators)

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:

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

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:
>     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?

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

int count = 0;

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

Quote:
}

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.

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
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

Quote:

>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:

>    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?

Vincent Fatica

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

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:
>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 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

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:
> >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 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.

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.

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:
> 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:

>     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?

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

Quote:
};

--
Later,
Jerry.

The universe is a figment of its own imagination.

Sun, 21 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:

>How would I implement countTheBits()?

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
Bitstrng.C   any  Print binary formatted strings
Bstr_I.C     any  Convert binary string to int

--
Wayne A. King

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
Quote:
>    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:

>    assert(cBitCount==28);

>    How would I implement countTheBits()?

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;
}

Quote:
}

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

Quote:
}

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

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
: 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:

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

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:

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;

Quote:
}

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.

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:

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

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

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:

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

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

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

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

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
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

--

Quote:

>>>unsigned long value = 1234567;
>>>int count;

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

>    Except that if value==0, you end up with a count of '1', where you
would
>expect it to be 0. Still, though, cool routine...

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)

Quote:
>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

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

Quote:
>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.

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.

Mon, 22 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
<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.

Tue, 23 Jul 2002 03:00:00 GMT
Bits Counting (using & and | operators)
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);

Quote:

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

Tue, 23 Jul 2002 03:00:00 GMT

 Page 1 of 2 [ 17 post ] Go to page: [1] [2]

Relevant Pages