CODEWITHSUNDEEP
c++arraysoperatorsbitwise-operators
Michel Jiang
Michel Jiang

Reputation: 601

Logical operation between all elements in array

I want to compare all items in my array using a boolean operator in the most efficient way. Currently, I have something like this :

bool myFunction(int i) 
{

    bool *myArray = {true, true, false, false, true};
    //suppose we know that i = 5 and that i is the length of the array...
    return myArray[0] && myArray[1] && myArray[2] && myArray[3] && myArray[4];
}

Since the size of the array is not fixed, the value of 'i' can change and my return statement would no longer be working, so I would have to implement something like this

bool myFunction(int i) 
{
    bool *myArray = //some other array of bools
    //should work with any value of i
    bool result = myArray[0];
    for (int a = 1; a < i; ++a)
    {
        result &= myArray[i];
    }
    return result;
}

I was wondering if there was a better way to do this other than making a for loop and going through each elements and comparing the value of the next item in list with the stored result from the previous two items. Like some bitwise operators that would make this easy or something, anything to take out the loop.

Upvotes: 1

Views: 7892

Answers (5)

Rama
Rama

Reputation: 3305

You can use a boost::dynamic_bitset, it has a member fuction any() that will return true if any bits in this bitset are set. And none() will return true if no bits are set.

But the implementation of any() is:

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::any() const
{
    for (size_type i = 0; i < num_blocks(); ++i)
        if (m_bits[i])
            return true;
    return false;
}

So you have inside a for loop!

But if you are searching for something like parallel computing, you may want to use arrayfire: For example it has an algorithm that do it. 

template<typename T >
T af::allTrue(  const array &   in  )   
//C++ Interface for checking if all values in an array are true.

Upvotes: 0

barak manos
barak manos

Reputation: 30136

You can exit the loop as soon as you encounter false:

for (int a = 0; a < i; a++)
{
    if (!myArray[i])
        return false;
}
return true;

If you're allowed to change the last value in the array, then here's a trick for optimizing it:

  • If the last value in the array is false, then return false
  • Write false into the last entry in the array
  • Iterate the array until you encounter false
  • Write true into the last entry in the array
  • If you stopped before the last entry, then return false
  • Return true

The code:

int a;
if (!myArray[i-1])
    return false;
myArray[i-1] = false;
for (a = 0; a < i; a++)
{
    if (!myArray[i])
        break;
}
myArray[i-1] = true;
return a != i-1;

This yields one branch per iteration instead of two branches per iteration.

If you're allowed to allocate i+1 entries, then you can get rid of the "last entry swapping" part:

int a;
myArray[i] = false;
for (a = 0; myArray[i]; i++);
return a != i;

You can also get rid of the additional arithmetic embedded in myArray[i]:

bool *arrayPtr;
myArray[i] = false;
for (arrayPtr = myArray; *arrayPtr; arrayPtr++);
return arrayPtr != myArray+i;

If the compiler doesn't already apply it, then this function will do so for sure. On the other hand, it might make it harder on the optimizer to unroll the loop, so you will have to verify that in the generated assembly code...

Upvotes: 0

Steranoid
Steranoid

Reputation: 30

I would change the condition of your for-loop so you won't continue if you encounter a false value and use an iterator instead of an index.

bool myFunction(int i) {
    bool myArray[i] = //some other array of bools
    //should workwith any value of i

    bool result;
    bool * a;
    for (a = myArray, result = *a; a < myArray+i && result; result=*(++i)) {}
    //no need to use the AND operator since we stop if we meet one false

    return result;
}

Or if you really prefer with index:

bool myFunction(int i) {
    bool myArray[i] = //some other array of bools
    //should workwith any value of i

    bool result;
    unsigned int a;
    for (a = 0, result = myArray[a]; a < i && result; result=myArray[++i]) {}
    //no need to use the AND operator since we stop if we meet one false

    return result;
}

Maybe I'm wrong, but I wouldn't use the bitwise AND assignment (&=) if it's not on bit range operation, it's not really relevant on the bool type though.

Upvotes: 0

Nazar554
Nazar554

Reputation: 4195

You can use all_of (replacestd::begin(myArray) + i with std::end(myArray) if you want to check entire array and not first i elements):

#include <vector>
#include <algorithm>
bool myFunction(int i)
{
    std::vector<bool> myArray = { true, true, false, false, true };
    return std::all_of(std::begin(myArray), std::begin(myArray) + i, [](bool elem) { return elem; });
}

Upvotes: 2

Mark Adelsberger
Mark Adelsberger

Reputation: 45769

You probably need to know that &= is not a logical operator; it is the "bitwise and" operator. As long as you only use it on booleans, I guess it will work ok; but C won't stop a value other than 1 or 0 from slipping into the array, so you should probably not make that assumption. Semantically if you're doing a logical or you want && instead of &.

That said, you can certainly use short-circuiting to refine what you're doing. Once you've found a single 0 (false), nothing from then on is going to make your aggregate go back to 1 (true), so you might as well stop.

for (int a = 1; result && a < i; ++a)
{
    result &= myArray[i];
}

Other than that, there's not much you can improve. Not sure why you're averse to a loop, but if you want to combine an unknown number of values you're going to have to iterate. You might find (or write) some utility function to do it, but it'll be using a loop internally anyway. (Unless it tries to leverage a vector processor that natively does what you want, maybe... but that would be rather pointless and, if you truly don't have a limit on number of values, will still involve a loop.)

Upvotes: 1

Related Questions