optimize binary increment loop

Question

Earlier today I asked a question regarding getting every possible combinations and I was given a good hint on using a binary loop, after some thoughts into it I came up with the following code in C++:

    vector<bool>binary(size,0);

bool filled=false;
while(filled==false)
{

    bool setdigit=true;
    for(int k=0;k<size;k++)
    {
        if(setdigit==true)
        {
            if(binary[k]==false) 
            {
                    binary[k]=true;
                    setdigit=false;
            }
            else //when the digit is already true
            {
                binary[k]=false;
            }
        }
    }
    for(int i=0;i<size;i++)
    {
        if(binary[i]==false) 
            {
                filled=false;
                break;
        }
        else filled=true;
    }
}

The code seems to work but the way to test whether the binary increment is finished is very badly coded, how should i go to improve the exit condition or even the looping process?

This won't optimize the speed of the code, but for readability and to reduce the possibility of error, I would get rid of all the "==true" and "==false". So `if(setdigit==true)` should just be `if(setdigit)`, and `if(binary[k]==false)` should just be `if(!binary[k])`. — Dan Korn, Jun 09 '14 at 21:11
Could you explain what you're trying to do and what you want to improve about the code? — Praxeolitic, Jun 09 '14 at 21:11
@Praxeolitic http://stackoverflow.com/questions/24126368/c-not-in-order-combination-of-array-elements is my original question, I just want to learn any tips on how to code better :) — tom, Jun 09 '14 at 21:13
@tom: I think it would make more sense to add a `do_task(binary)` in the middle, to clarify that this loop has a purpose. — Mooing Duck, Jun 09 '14 at 21:43

score 4 · Answer 1 · answered Jun 09 '14 at 21:11

4

pseudo code:

for (i=0;i<2^size;i++)
   binary = std::bitset(i);  /* the bits of i are the bits you are looking for */

answered Jun 09 '14 at 21:11

AShelly

34,686
15
91
152

thanks for the tip! I am using the loops to find permutations of a set of numbers so not just getting binary only – tom Jun 09 '14 at 21:26
Treat a `1` as `true` and there should be no logical difference between a `bitset` and a `vector`. – AShelly Jun 09 '14 at 21:36

Jarod42 · Answer 2 · 2014-06-09T22:31:40.670

Your setdigit is useless. you may remove it, remove the condition, and replace the assignation to false by a break. So the loop would be

for(int k = 0; k < size; k++)
{
    if (binary[k] == false) 
    {
        binary[k] = true;
        break;
    }
    else // when the digit is already true
    {
        binary[k] = false;
    }
}

You may then change your while (filled /* has only true */)
by a do {} while(binary_is_false /* has only false */)
to allow to do the check directly inside the increment.

You may finally split your code into function to obtain something like: (https://ideone.com/dmQwFc)

bool increase(std::vector<bool>& v)
{
    for (std::size_t i = 0; i != v.size(); ++i) {
        v[i] = !v[i];
        if (v[i] == true) {
            return true;
        }
    }
    return false; // v contains only false values now.
}

int main()
{
    std::vector<bool> v(5);

    do {
        // Do some job as printing vector content:
        for (std::size_t i = 0; i != v.size(); ++i) {
            std::cout << v[i] << " ";
        }
        std::cout << std::endl;
    } while (increase(v));
    return 0;
}

score 0 · Answer 3 · answered Jun 09 '14 at 21:17

You can change the code:

for(int i=0;i<size;i++)
    {
        if(binary[i]==false) 
            {
                filled=false;
                break;
        }
        else filled=true;
    }

by

filled = (find(binary.begin(), binary.end(), false) == binary.end())

you need to include <algorithm> for this work.

optimize binary increment loop

3 Answers3

Linked