CODEWITHSUNDEEP
c++cbinarybit-manipulationbit
Heisenbug
Heisenbug

Reputation: 39164

Efficient bitwise operations for counting bits or find the right|left most ones

Given an unsigned int, I have to implement the following operations :

  1. Count the number of bits set to 1
  2. Find the index of the left-most 1 bit
  3. Find the index of the righ-most 1 bit

(the operation should not be architecture dependents).

I've done this using bitwise shift, but I have to iterate through almost all the bits(es.32) . For example, counting 1's:

unsigned int number= ...;
while(number != 0){
    if ((number & 0x01) != 0)
        ++count;
    number >>=1;
}

The others operation are similar.

So my question is: is there any faster way to do that?

Upvotes: 10

Views: 10078

Answers (6)

Ranoiaetep
Ranoiaetep

Reputation: 6637

With C++20, these operations can be done easily with the newly added header, <bit>.

  1. popcount
  2. countl_one
  3. countr_one

Each of them would then call compiler specific functions like __popcnt() and __builtin_popcount().

Upvotes: 4

Tushar Nikam
Tushar Nikam

Reputation: 1593

for rightmost bit simple ans

First Method

unsigned int getFirstSetBit(int n){

return log2(n & -n) + 1;

}

Second Method

unsigned int getFirstSetBit(int n){

return ffs(n);

}

Upvotes: 1

paetz
paetz

Reputation: 31

"The righ-most 1 bit" of number x is given by

pos(1st '1') = log_2(x XOR (x-1) + 1) - 1

E.g.:

x               = 1100101000;
x-1             = 1100100111;
x XOR (x-1)     = 0000001111;
x XOR (x-1) + 1 = 0000010000;

The base2-log of the last line then gives you the correct position + 1. So substract 1 from the log-result and you'll have the most-right '1' bit.

For the most-right '0' bit you may use 

pos(1st '0') = log_2(x XOR (x+1) + 1) - 1

Upvotes: 3

Mysticial
Mysticial

Reputation: 471199

If you want the fastest way, you will need to use non-portable methods.

Windows/MSVC:

GCC:

These typically map directly to native hardware instructions. So it doesn't get much faster than these.

But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.

Upvotes: 11

Frerich Raabe
Frerich Raabe

Reputation: 94289

Quoting from http://graphics.stanford.edu/~seander/bithacks.html

The best method for counting bits in a 32-bit integer v is the following:

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

The best bit counting method takes only 12 operations, which is the same as the lookup-table method, but avoids the memory and potential cache misses of a table. It is a hybrid between the purely parallel method above and the earlier methods using multiplies (in the section on counting bits with 64-bit instructions), though it doesn't use 64-bit instructions. The counts of bits set in the bytes is done in parallel, and the sum total of the bits set in the bytes is computed by multiplying by 0x1010101 and shifting right 24 bits.

Upvotes: 6

Daniel Eggert
Daniel Eggert

Reputation: 6715

Take a look at ffs(3), ffsl(3), fls(3), flsl(3).

The ffs() and ffsl() functions find the first bit set (beginning with the least significant bit) in i and return the index of that bit.

The fls() and flsl() functions find the last bit set in i and return the index of that bit.

You might be interested in bitstring(3), too.

Upvotes: 10

Related Questions