代码之家 › 专栏 › 技术社区 › fmsf

如何知道数组的值是否由零组成?

bytearray memory-management c++

fmsf · 技术社区 · 14 年前

嘿,如果你能得到更具描述性的标题,请编辑它。

我正在写一个小算法,它涉及检查矩阵中的值。假设:

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

假设我用一对1的值(5或6)填充矩阵,比如:

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

例如,我如何知道矩阵区间的二进制值是否为零(在伪代码中)

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

我想重新学习C/C++。应该有一种方法来挑选这一百个字节(它们彼此相邻)并检查它们的值是否都是零,而不必逐个检查。(考虑到char是一个字节)

6 回复 | 直到 14 年前

R Samuel Klatchko 14 年前

您可以使用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

您也可以使用活页夹删除自由功能(尽管我认为活页夹很难阅读):

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

当,我只是注意到请求不要一个字节一个字节地做这个。尽管隐藏了,但仍然可以逐字节查找。尽管使用更大的类型会有所帮助,但您必须1比1完成此操作。这是我的最终版本。

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);
    }
}

这首先要检查数据是否足够长,使其值得使用更复杂的算法。我不是100%肯定这是必要的,但你可以调整什么是最低限度的必要。

假设数据足够长,它首先对齐开始和结束指针,以匹配用于进行比较的类型的对齐方式。然后,它使用新类型检查大量数据。

我建议使用:

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)

Adam Rosenfield 14 年前

没有内置的语言功能可以做到这一点,也没有标准的库函数可以做到这一点。 memcmp() 可以,但是您需要第二个包含所有零的数组来进行比较;该数组必须很大,并且在进行比较时也会占用不必要的内存带宽。

你自己写函数就行了,没那么难。如果这确实是您的应用程序的瓶颈(您应该只得出以下结论分析 ,然后在程序集中重写该函数。

Chris H 14 年前

您标记了这个C++,因此可以使用指针作为迭代器,并使用STL算法。std::max。然后查看max是否为0。

Anon. 14 年前

你可以把你的指针 int * 然后一次检查四个字节而不是一个。

wilhelmtell 14 年前

除了逐个检查所有元素之外,无法判断数组是否有除零以外的任何值。但是,如果您从一个数组开始,知道它都是零的,那么您可以维护一个标志来说明数组的零状态。

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

// ...

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

// ...

if( allzeroes ) {
    // ...
}

EvilTeach 14 年前

保留数组的元素0,设置为所有零。

使用memcmp比较两个元素中的对应范围。