Calculate how many ones in bits and bits inverting

Question

Possible Duplicate:
How many 1s in an n-bit integer?

Hello

How to calculate how many ones in bits?

1100110 -> 4
101 -> 2

And second question:

How to invert bits?

1100110 -> 0011001
101 -> 010

Thanks

Many duplicates, e.g. [How many 1s in an n-bit integer?](http://stackoverflow.com/questions/1611333/how-many-1s-in-an-n-bit-integer) and [What does this function do?](http://stackoverflow.com/questions/3265942/what-does-this-function-do). Also should really be two separate questions. — Paul R, Mar 28 '11 at 08:36
also should ask second question in a separate question anyway — jk., Mar 28 '11 at 09:42

score 5 · Answer 1 · answered Mar 28 '11 at 08:33

5

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.

answered Mar 28 '11 at 08:33

Björn Pollex

75,346
28
201
283

+1: this ties in better with the question than `~`, flipping bits without rounding the number of bits up to the size of the data type. – Tony Delroy Mar 28 '11 at 09:35

score 4 · Answer 2 · edited May 23 '17 at 12:11

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?

score 3 · Accepted Answer · answered Mar 28 '11 at 08:32

3

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;
}
```
You use the ~ operator.

answered Mar 28 '11 at 08:32

Sylvain Defresne

42,429
12
75
85

Thank you! How to cout bits? I mean instead of 5 -> I want to see 101 – VextoR Mar 28 '11 at 08:48
1

Use `std::bitset` : `std::bitset<32> bitset(5); std::cout << bitset << std::endl;`. – Sylvain Defresne Mar 28 '11 at 08:55

score 1 · Answer 4 · answered Mar 28 '11 at 08:32

1

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

Inverting bits: x = ~x;

answered Mar 28 '11 at 08:32

Erik

88,732
13
198
189

score 1 · Answer 5 · answered Mar 28 '11 at 08:33

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.

score 1 · Answer 6 · answered Mar 28 '11 at 08:36

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;

score 1 · Answer 7 · answered Mar 28 '11 at 09:02

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

Agnius Vasiliauskas · Answer 8 · 2011-03-28T10:03:41.367

1

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

edited Mar 28 '11 at 10:03

answered Mar 28 '11 at 09:56

Agnius Vasiliauskas

10,935
5
50
70

score 0 · Answer 9 · answered Mar 28 '11 at 09:04

0

How to calculate how many ones in bits?

Hamming weight.

How to invert bits?

i = ~i;

answered Mar 28 '11 at 09:04

Prince John Wesley

62,492
12
87
94

Calculate how many ones in bits and bits inverting

9 Answers9