Fastest way to count consecutive 1 bits. C++

Question

Basicly I just need to know the position of the highest 1 bit inside of an int or unsigned int. Like:

00001111=4;
00011111=5;
11111111=8;

Because I am sure that any number I will get will have consecutive 1 bits. 0...0000011...1 There will be no ..00010011... or something. So method can find the highest 1 or just count 1s. No matter.

This is the best I managed to do:

Uint32 number;
int shift=16; int segment=8;
while (segment) 
{
if (number>>shift!=0) shift+=segment; 
else shift-=segment;
segment>>1; // /2
}

Answer 1

you can try something like

    std::bitset<32> b1; 
    int i_num;
    std::cin>> i_num;
    b1=i_num;
   if(b1[31]==1)
      return 31;
   else if(b1[30]==1)
      return 30;
     ---------
  else if(b1[0]==1)
 return 0;
 else
 reutrn -1;

Answer 2

int count_bit(unsigned int num) {
    // Assume 0<= num < 256, i.e. 8 bit
    // It can be easily support larger word size by successive calling.
    if ( num >= 256 ) return -1;
    return count[ num ];
}

Yes, the fastest way is lookup table.

Answer 3

(1)

you could count how many times you would have to bitshift your unsigned int until it was zero?

see What are bitwise shift (bit-shift) operators and how do they work?

or

(2)

example

number: 0111

bitshift one to the right: 0011, use bitwise x-or with original number 0111 ^ 0011 = 0100

in cpp:

unsigned int num = 3;

unsigned int answer = ((num >> 1) ^ (num)); 

cout << answer << '\n';

Answer 4

Others have given a variety of answers, but it's probably worth mentioning that there is an entire book full of these kinds of things — Hacker's Delight by Henry S. Warren Jr., ISBN 978-0-201-91465-8, which also has a web page.

It's also worth highlighting the fact that some microprocessors have special support for some of these kinds of things. Lasse Reinhold's answer, above, makes use of that fact, but doesn't call the reader's attention to it. Generally speaking, except for very simple cases (like bit rotate instructions), compilers can't optimise “bit twiddling” algorithms to a single machine instruction, so if you know you’re on a machine that has e.g. a bit-scan-forward or population count instruction or similar, and you're in a position to use it (via either compiler intrinsics or asm statements), you might want to do so.

Finally, since the question started by saying that the number was known to be of the form 0...000111...1, I'll add another option, based on computing (in parallel) the sums of the groups of bits:

uint32_t count_set_bits(uint32_t x) {
  x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
  x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
  x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
  x = ((x >> 8) + x) & 0x00ff00ff);
  return (x >> 16) + x) & 0x0000ffff;
}

Answer 5

Below code might help to count consecutive 1 bits.

int count_consecutive_ones(int in) {
    int count = 0;
    while (in) {
        in = (in & (in << 1));
        count++;
    }
    return count;
}

Answer 6

Copy/paste of my function for it:

size_t FirstSetBit(unsigned int v) const
{
#if defined(_MSC_VER)
    unsigned long ul;
    // Just 10% faster than MultiplyDeBruijnBitPosition method, on Core i7
    _BitScanForward(&ul, v);
    return ul;
#elif defined(__GNUC__) || defined(__clang__)
    return 31 - __builtin_clz(v);
#else // integer fallback for non-x64
    #warning You may be able to optimise this code for your compiler/processor

    int r;
    static const int MultiplyDeBruijnBitPosition[32] =
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    r = MultiplyDeBruijnBitPosition[(uint32_t((v & -int(v)) * 0x077CB531U)) >> 27];
return r;
#endif
}