Bits Counting (using & and  operators)
Author 
Message 
David Sworde #1 / 17

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


Erik Funkenbusc #2 / 17

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 nonzero. 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; unsigned long lSubnetMask=0xfffffff0; 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 


Vincent Fatic #3 / 17

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 ... thirtytwo "if"s written in assembly with hardcoded 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: > 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 nonzero. 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 


David Sworde #4 / 17

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 


Erik Funkenbusc #5 / 17

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 


Jerry Coffi #6 / 17

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: > 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 nonzero. 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 8bit 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 


Wayne A. Ki #7 / 17

Bits Counting (using & and  operators)
Quote:
>How would I implement countTheBits()?
Go to http://www.snippets.org and look at: Bitlevel 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 lookup) Bitcnt_4.C any Count bits in a number (recursive table lookup) 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

Mon, 22 Jul 2002 03:00:00 GMT 


JeanFrancois Bocque #8 / 17

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: > unsigned long lSubnetMask=0xfffffff0; > char cBitCount=countTheBits(lSubnetMask); > 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 


Ben Hutchin #9 / 17

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: : 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 nonzero. 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 1bit counters to be summed */ unsigned long count = (lSubnetMask & 0x55555555) + ((lSubnetMask & 0xAAAAAAAA) >> 1); /* count contains 16 2bit counters to be summed */ count = (count & 0x33333333) + ((count & 0xCCCCCCCC) >> 2); /* count contains 8 4bit counters to be summed */ count = (count & 0x0F0F0F0F) + ((count & 0xF0F0F0F0) >> 4); /* count contains 4 8bit counters to be summed */ count = (count & 0x00FF00FF) + ((count & 0xFF00FF00) >> 8); /* count contains 2 16bit 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 1bits 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; Quote: }
but I doubt that it's faster  conditional branches can be slow.  Any opinions expressed are my own and not necessarily those of LaserScan.

Mon, 22 Jul 2002 03:00:00 GMT 


Andrew Koen #10 / 17

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


Karl Heinz Buchegge #11 / 17

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 highorder 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 1bits.  Karl Heinz Buchegger

Mon, 22 Jul 2002 03:00:00 GMT 


James Brow #12 / 17

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 nonzero!) (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 rightmost 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. Quote:
>>>How about this one: >>>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 


David Sworde #13 / 17

Bits Counting (using & and  operators)
Quote: >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.
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". 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 1bits.
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 


Ben Hutchin #14 / 17

Bits Counting (using & and  operators)
<snip> : Your problem is more specific, in that all the 1bits 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 LaserScan.

Tue, 23 Jul 2002 03:00:00 GMT 


Rufus V. Smit #15 / 17

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 1bits 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 LaserScan.

Tue, 23 Jul 2002 03:00:00 GMT 


Page 1 of 2

[ 17 post ] 

Go to page:
[1]
[2] 
