Calculate how many ones in bits and bits inverting [duplicate]
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?
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.
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;
精彩评论