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 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 |
|
 |
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 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; 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 ... 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: > 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?
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 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 |
|
 |
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: 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
|
Mon, 22 Jul 2002 03:00:00 GMT |
|
 |
Jean-Francois 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 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; 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 |
|
 |
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 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 |
|
 |
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 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
|
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 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. 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 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 |
|
 |
Ben Hutchin #14 / 17
|
 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 |
|
 |
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 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] |
|