Ask Your Question

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

asked 2017-02-10 02:48:39 -0500

zms gravatar image

hi, if i have a string of binary number scan from a binary image from this code

     for( int y=0; y< frame_gray.rows; y+=10){
    for (int x=0;x< frame_gray.cols;x+=1){

        if (<uchar>(y,x)==0)
        {  cout << "0 binary=" << endl;}

        {  cout << "1 binary=" << endl;width++;}


    cout << "width=" << width << endl;
    cout << "new pixel line" << endl;

as example output is 0000000111111000000, how can i write a code to tell me there is two times of value transition 0-->1 and 1--->0? or

00001111100000111100000 there are 4 times of transition happened.


edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2017-02-11 02:29:45 -0500

berak gravatar image

the general idea is:

  1. bitwise shift to the right
  2. xor with original value, so only transition bits are left
  3. count remaining bits

here's a demo implementation, using std::bitset (for demo purpose), same idea works with uints, too, ofc.

#include <bitset>
bitset<24> a("00001111100000111100000");
// 000001111100000111100000
auto b = a >> 1;
// 000000111110000011110000
auto c = a ^ b;
// 000001000010000100010000
auto len = c.count();  // popcnt() , if you use integers.
// 4
edit flag offensive delete link more


to make it as bitset, the output as in 0000001111110000 should be converted to string then bitset? Or is it possible just to take the string from the Mat array [1x50] and convert it, into bitset to perform the operation?

zms gravatar imagezms ( 2017-02-13 04:18:42 -0500 )edit

answered 2017-02-11 07:52:48 -0500

Eduardo gravatar image

updated 2017-02-11 08:48:22 -0500


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).


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.


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.

edit flag offensive delete link more

Question Tools

1 follower


Asked: 2017-02-10 02:48:39 -0500

Seen: 347 times

Last updated: Feb 11 '17