how to know there is a transition in a string of binary numbers

edit

Edit2:

A much simpler solution should be to just count the number of times the current value is different of the next value (demo code here).

Edit:

The size of a bitset cannot be dynamic (the size is fixed at the compilation). You can use dynamic_bitset from Boost instead or just allocate a big size and fill from 1 to avoid the mentioned issues above (no need to pad here).

I extended the answer of @berak to be able to handle edge cases as:

• binary shift to the right will "lose" the value of the first bit (or least significant bit): 01 >> 1 produces 00
• binary shift to the right will introduce a 0 for the last bit (or most significant bit): 11 >> 1 produces 01

To solve this issue, I increase the size of the bitset by 2 and I pad the least and most significant bit with the values of the original bitset. The XOR is performed only on the same bit positions than the original bitset.

If you want to count the number of transitions on a horizontal scan line (for a binary image), you can iterate over the image and fill a bitset for each row.

Implementation:

template<int N>
size_t transitionCount2(const std::bitset<N> &b)
{
    assert(N > 0);
    if (N <= 1)
        return 0;

    std::bitset<N+2> b_pad;
    b_pad.set(0, b[0]); //pad with the least significant bit
    b_pad.set(N+1, b[N-1]); //pad with the most significant bit

    for (size_t i = 0; i < b.size(); i++)
    {
        b_pad[i+1] = b[i];
    }

    auto c = b_pad >> 1;
    std::bitset<N> c_pad_cut;
    for (size_t i = 0; i < c_pad_cut.size(); i++)
    {
        c_pad_cut[i] = c[i+1];
    }

    auto d = b ^ c_pad_cut;
    return d.count();
}

The full test code can be executed here.