c - 关于哈希函数

Question

让我们考虑一个二维数组，声明如下:

#include <stdbool.h>

bool array[N1][N2];

我必须知道这个数组的每一行是否恰好有一个true相同位置的值。

例如以下内容就可以:

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 0, 1 },
  { 0, 0, 1, 1 }
}

然而这是不正确的:

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 1, 0 },
  { 0, 0, 1, 1 }
}

我已经尝试过这个:

static uintmax_t hash(const bool *t, size_t n) 
{
    uintmax_t retv = 0U;
    for (size_t i = 0; i < n; ++i)
        if (t[i] == true)
            retv |= 1 << i;
    return retv;
}

static int is_valid(bool n) 
{ 
    return n != 0 && (n & (n - 1)) == 0;
}

bool check(bool t[N1][N2])
{
    uintmax_t thash[N1];

    for (size_t i = 0; i < N1; ++i)
        thash[i] = hash(t[i], N2);

    for (size_t i = 0; i < N1; ++i)
        for (size_t j = 0; j < N1; ++j)
            if (i != j && !is_valid(thash[i] & thash[j]))
                return 0;

    return 1;
}

但它仅适用于 N1 <= sizeof(uintmax_t) * CHAR_BIT 。你知道解决这个问题的最佳方法吗？

Answer 1

为什么不创建另一个大小为 N2(列数)的数组，将其设置为全部 true，然后将其设置为每行中的每一列。最后，检查您的新数组是否恰好有一个设置位。

bool array[N1][N2];  // this is initialized somehow
bool result[N2];
int i, j;

// initialize result array
for (j = 0; j < N2; ++j)
{
    result[j] = 1;
}

// Now go through the array, computing the result
for (i = 0; i < N1; ++i)
{
    for (j = 0; j < N2; ++j)
    {
        result[j] &= array[i][j];
    }
}

// At this point, you can check the result array.
// If your array is valid, then result should have only one '1' in it.