Calculate how many ones in bits and bits inverting [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

How many 1s in an n-bit integer?

Hello

How to calculate how many ones in bits?

1100110 -> 4
101 -&g开发者_StackOverflow中文版t; 2

And second question:

How to invert bits?

1100110 -> 0011001
101 -> 010

Thanks

---

If you can get your bits into a std::bitset, you can use the flip method to invert, and the count method to count the bits.

---

The book Hacker's Delight by Henry S Warren Jr. contains lots of useful little gems on computing this sort of thing - and lots else besides. Everyone who does low level bit twiddling should have a copy :)

The counting-1s section is 8 pages long!

One of them is:

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

A potentially critical advantage compared to the looping options already presented is that the runtime is not variable. If it's inside a hard-real-time interrupt service routine this is much more important than "fastest-average-computation" time.

There's also a long thread on bit counting here: How to count the number of set bits in a 32-bit integer?

---

1. You can loop while the number is non-zero, and increment a counter when the last bit is set. Or if you are working on Intel architecture, you can use the popcnt instruction in inline assembly.

   int count_bit_set(unsigned int x) {
       int count = 0;
       while (x != 0) {
           count += (x & 1);
           x = x >> 1;
       }
       return count;
   }
   

2. You use the ~ operator.

---

Counting bits: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Inverting bits: x = ~x;

---

For the first question, Fast Bit Counting has a few ways of doing it, the simplest being:

int bitcount (unsigned int n) {
   int count = 0;
   while (n) {
      count += n & 0x1u;
      n >>= 1;
   }
   return count;
}

For the second question, use the ´~´ (bitwise negation) operator.

---

To count the number of set bits in a number you can use the hakmem parallel counting which is the fastest approach not using predefined tables for parallel counting:

http://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/

while inverting bits is really easy:

i = ~i;

---

A somewhat trikcy (but faster) solution would be:

int setbitcount( unsigned int x )
{
    int result;
    for( result=0; x; x&=x-1, ++result )
        ;
    return result;
}

Compared to sylvain's soultion, this function iterates in the loop only the number of set bits. That is: for the number 1100110, it will do only 4 iteration (compared to 32 in Sylvain's algorithm).

The key is the expression x&=x-1, which will clear the least significant set bit. i.e.:
1) 1100110 & 1100101 = 1100100
2) 1100100 & 1100011 = 1100000
3) 1100000 & 1011111 = 1000000
4) 1000000 & 0111111 = 0

---

You can also inverse bits by XOR'ing them with some number.
For example - inversing byte: INVERTED_BYTE = BYTE ^ 0xFF

---

How to calculate how many ones in bits?

Hamming weight.

How to invert bits?

i = ~i;