How to know if the the value of an array is composed by zeros?

Question

Hey, if you can get a more descriptive tittle please edit it.

I'm writing a little algorithm that involves checking values in a matrix. Let's say:

char matrix[100][100];
char *ptr = &matrix[0][0];

imagine i populate the matrix with a couple of values (5 or 6) of 1, like:

matrix[20][35]=1;
matrix[67][34]=1;

How can I know if the binary value of an interval of the matrix is zero, for example (in pseudo code)

if((the value from ptr+100 to ptr+200)==0){ ... // do something

I'm trying to pick up on c/c++ again. There should be a way of picking those one hundred bytes (which are all next to each other) and check if their value is all zeros without having to check on by one.(considering char is one byte)

Answer 1

You could cast your pointer as an int * and then check four bytes at a time rather than one.

Answer 2

There's no built-in language feature to do that, nor is there a standard library function to do it. memcmp() could work, but you'd need a second array of all zeroes to compare against; that array would have to be large, and you'd also eat up unnecessary memory bandwidth in doing the comparison.

Just write the function yourself, it's not that hard. If this truly is the bottleneck of your application (which you should only conclude of profiling), then rewrite that function in assembly.

Answer 3

you tagged this C++, so you can use a pointer as an iterator, and use an stl algorithm. std::max. Then see if the max is 0 or not.

Answer 4

You can use std::find_if.

bool not_0(char c)
{
    return c != 0;
}

char *next = std::find_if(ptr + 100, ptr + 200, not_0);
if (next == ptr + 200)
    // all 0's

You can also use binders to remove the free function (although I think binders are hard to read):

char *next = std::find_if(ptr + 100, ptr + 200,
                           std::bind2nd(std::not_equal_to<char>(), 0));

Dang, I just notice request not to do this byte by byte. find_if will still do byte by byte although it's hidden. You will have to do this 1 by 1 although using a larger type will help. Here's my final version.

template <class T>
bool all_0(const char *begin, const char *end, ssize_t cutoff = 10)
{
    if (end - begin < cutoff)
    {
        const char *next = std::find_if(begin, end,
           std::bind2nd(std::not_equal_to<char>(), 0));
        return (next == end);
    }
    else
    {
        while ((begin < end) && ((reinterpret_cast<uintptr_t>(begin) % sizeof(T)) != 0))
        {
            if (*begin != '\0')
                return false;

            ++begin;
        }

        while ((end > begin) && ((reinterpret_cast<uintptr_t>(end) % sizeof(T)) != 0))
        {
            --end;

           if (*end != '\0')
               return false;
        }

        const T *nbegin = reinterpret_cast<const T *>(begin);
        const T *nend = reinterpret_cast<const T *>(end);

        const T *next = std::find_if(nbegin, nend,
           std::bind2nd(std::not_equal_to<T>(), 0));
        return (next == nend);
    }
}

What this does is first checks to see if the data is long enough to make it worth the more complex algorithm. I'm not 100% sure this is necessary but you can tune what is the minimum necessary.

Assuming the data is long enough it first aligns the begin and end pointers to match the alignment of the type used to do the comparisons. It then uses the new type to check the bulk of the data.

I would recommend using:

all_0<int>(); // 32 bit platforms
all_0<long>(); // 64 bit LP64 platforms (most (all?) Unix platforms)
all_0<long long>() // 64 bit LLP64 platforms (Windows)

Answer 5

There's no way to tell whether an array has any value other than zero other than by checking all elements one by one. But if you start with an array that you know has all zeros, then you can maintain a flag that states the array's zero state.

std::vector<int> vec(SIZE);
bool allzeroes = true;

// ...

vec[SIZE/2] = 1;
allzeroes = false;

// ...

if( allzeroes ) {
    // ...
}

Answer 6

Reserve element 0 of your array, to be set to all zeros.

Use memcmp to compare the corresponding ranges in the two elements.