在C语言中，我们需要比较数组的每个元素吗？

Question

I have the following code:

int isUsed[6] = {1,1,1,1,1,1};

如何比较此数组中的所有元素是否都等于1或其他值？ 我知道我们可以循环遍历数组并逐个进行比较，但是我们有没有其他方法来实现呢？

- user2131316

---

答案是否定的。不访问每个元素是不可能的。 - Dayal rai

你为什么不满意已知的方法，即循环数组并逐个比较元素？你觉得这种方法不够优化吗？如果是这样，为什么？ - Daniel Daranas

是的，我觉得如果我们有一个C库方法会更好。 - user2131316

@user2131316：为了满足这种复杂度的每个需求都有库方法，需要添加大量函数，其中任何一个都不会经常使用。我更希望他们添加库函数，使得目前难以自己编写的东西变得容易。（如果你想要这种便利，C++有标准库函数...） - Tony Delroy

Answer 1

是的，你必须一个元素一个元素地进行操作。

如果你的数组只包含纯整数类型（即不是由struct组成的数组），并且你只想检查它们是否相等，可以使用memcmp()。

当然，这个函数会在内部循环，但它是一个预先制作的标准函数，因此有助于可读性。但是，它可能会降低性能，因为它比较的是char。另一方面（根据评论），由于它是一个众所周知的库函数，可能会被优化，从而提高性能。

此外，为了完整起见，我之前提到struct时有一个警告，因为结构体通常包含填充字节，这些字节将被memcmp()“看到”，并可能导致错误的结果。

例如：

struct {
  int x;
  char y;
  int z;
} a = { 1, 2, 3 }, b = { 1, 2, 3 };

在许多系统上，上述struct的y和z之间会有填充，这可能会导致memcmp()返回错误结果，因为填充字节具有未定义的值。

- unwind

---

举例来说，int x[100]，y[100];，memcmp()必须进行400个字节大小的比较（假设 sizeof(int)==4）。只需要对 int 进行比较的应用程序循环需要100次，这可能会产生差异。我说“可能”。@johnchen902 - unwind

@unwind 我不能给你的评论第二个赞。不错，谢谢！ - Grijesh Chauhan

@GrijeshChauhan 不可以。在C语言中，结构体没有==运算符。赋值(=)是可以的，但是没有比较。 - unwind

@unwind 哦！我错了，你是正确的，我混淆了 = 和 ==，对于结构体来说，== 是无效的。 - Grijesh Chauhan

@unwind memcmp 不会 进行 400 字节的比较。查看好的库源代码，它将使用机器的字长（例如64位）进行比较，并进行 QWORD 对齐的内存访问。通常无法在简单循环中超越这种方法。 - rubber boots

Answer 2

对于原始数据类型（不包括结构体），如果您知道数组的大小和您想要比较的内容：memcmp可以完成工作：

#include <stdio.h>
#include <string.h>

static int allOnes[6] = {1,1,1,1,1,1};

int main(int argc, const char* argv[]) {

   int isUsed[6] = {1,1,1,1,1,1};

   if( memcmp( isUsed, allOnes, sizeof allOnes ) == 0 )
       printf( "Array has only 1's\n" );
   else
       printf( "At least one element is not 1\n" );
}

---

编辑：关于性能...

一些评论提到了memcmp和循环（包括展开循环）的性能。

下面是一个简单的测试程序来衡量性能。在我的机器上（Mac OS X，LLVM编译器），我得到以下结果：

memcmp: 0.036031 seconds result=1
loop: 0.097180 seconds result=1
unrolled loop: 0.075623 seconds result=1

在对上述数字做出具体评论之前，请注意：

• 我并不是在做一个普遍性的声明，只是展示在我的环境中，memcmp解决方案大幅领先于其他解决方案。
• 我所使用的循环展开不是最优实现。这只是为了尝试一些循环展开的粗略尝试。

您可以随意重新设计代码并发布其他数字。

#include <stdio.h>
#include <string.h>
#include <time.h>

static int allOnes[6] = {1,1,1,1,1,1};

bool compareWithMemcmp()
{
       int isUsed[6] = {1,1,1,1,1,1};
       return memcmp( isUsed, allOnes, sizeof allOnes ) == 0;
}

bool compareWithLoop()
{
       int isUsed[6] = {1,1,1,1,1,1};
       for( int i = 0; i < sizeof allOnes / sizeof allOnes[0]; i++)
           if( isUsed[i] != 1 )
               return false;
       return true;
}

bool compareWithUnrolledLoop()
{
       int isUsed[6] = {1,1,1,1,1,1};
       // IMPORTANT: doesn't account for odd-length array
       for( int i = 0; i < sizeof allOnes / sizeof allOnes[0]; i += 2)
           if( (isUsed[i] != 1) || (isUsed[i+1] != 1) )
               return false;
       return true;
}

int main(int argc, const char* argv[]) {

    bool result;

    clock_t begin = clock();
    for( int i = 0; i < 10000000; i++ )
       result = compareWithMemcmp();
    printf( "memcmp: %f seconds result=%d\n",
            (double)(clock() - begin) / CLOCKS_PER_SEC, result );

    begin = clock();
    for( int i = 0; i < 10000000; i++ )
       result = compareWithLoop();
    printf( "loop: %f seconds result=%d\n",
            (double)(clock() - begin) / CLOCKS_PER_SEC, result );

    begin = clock();
    for( int i = 0; i < 10000000; i++ )
       result = compareWithUnrolledLoop();
    printf( "unrolled loop: %f seconds result=%d\n",
            (double)(clock() - begin) / CLOCKS_PER_SEC, result );
}

- Christian Garbin

Answer 3

你需要逐一比较数组元素。

- Yu Hao

Answer 4

我不同意任何说法，认为没有其他方法...

答案取决于数组可能如何更改。

假设你已经预先设置了一个已知值的数组，并且没有进一步的更改，那么测试就是微不足道的，解决方案是O(1)。它全部都是1，因为你这样做了。

一旦你开始改变值，如果有一些模式来改变它们，那么你可能能够记录关于该模式本身的信息，并且测试可以在小于O(n)的历史记录中进行。

例如，当你改变数组中的一个元素时，你可能会在其他地方设置一个标志，指示哪些部分需要重新评估。如果所有的修改都聚集在一个小区域内，那么你可能只需要测试数组的一小部分。

然而，在给定的特定示例中，一个小的isUsed[]数组，可以合理地假设每个元素只有两种可能的状态。如果你用一个位掩码来表示它，那么测试整个数组可能是一个单独的整数操作。它隐含地访问了每个元素，但比循环更有效率。

- sh1

Answer 5

没有其他方法，只能逐个比较每个元素。虽然这会减慢速度，但没有其他选择。尝试一下。

#define NULL (void*)0
memcmp(char* source, const char * dest, int count);

如果字符串匹配，则返回 NULL。

- Ishmeet

---

你的回答是Unwind的回答的复制，而且你所说的String是错误的。 - Grijesh Chauhan

解开：朋友，我没有看到你的消息。如果将null定义为#define NULL（void*）0，则为true。 - Ishmeet

Answer 6

你可以使用内联汇编，参考以下示例：

你可以编写一个宏来重复执行此代码6次，解决你的问题：

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>


int64_t isUsed[ 1 ] = { 1 };

int main ( void )
{

 __asm__
(
    "\n movq  %[a] , %%rax"
    "\n cmpq  $1 , %%rax"
    :
    : [ a ] "m" ( isUsed[0] )
);

__asm__ goto ("jne %l0\n"
: 
: 
: 
: NotEqual);


printf ("\n Array Contains 1 in all elements");
return 1 ;

NotEqual:

printf ("\n Array Not contains 1 in all elements");

return 0 ;
}

这是汇编代码：（小写）

 movq  isUsed(%rip) , %rax
 cmpq  $1 , %rax
 jne .L2

注意你将使用的整数类型（int32_t或int64_t：inttypes.h）

- user2107435

---

你可以这样做，但是很有可能你的代码会比编译器产生的代码慢得多，如果你提高了优化级别。玩汇编语言很有趣，而且打败编译器也是可能的 - 但除非你的名字是Agner Fog（或同样杰出的人），否则你的机会不大。 - Nik Bougalis

@NikBougalis，但是如果你不试图击败编译器，你怎么可能会得到像Agner Fog这样酷的名字呢？ - Grady Player

@gradyplayer，这是一个很好的观点 - 尝试并没有错。我确实说过玩汇编语言很有趣 ;) - Nik Bougalis

Answer 7

你可以使用GCC扩展：

#include <stdio.h>
#include <inttypes.h>

#define VECTOR_SIZE         4
typedef int v4int __attribute__ ((vector_size(sizeof(int32_t)*VECTOR_SIZE))); 


typedef union f4vector   
{
 v4int       v;
 __int128_t   value ;
} f4vector;



int main()
{
union f4vector a, b, c;

a.v = (v4int) { 1, 1, 1, 2 }; // your vector
b.v = (v4int) { 1, 1, 1, 1 };

c.v = a.v - b.v;

if ( c.value == 0 )
    puts ( "array contains all 1");
else
    puts ("array Not contais all 1");

return 0 ;
}

- user2107435