關於散列函數

讓我們考慮一個bidimensionnal陣列，聲明如下：關於散列函數

#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。你知道解決它的最好方法嗎？

來源

2012-11-01 md5

Oups，我想我沒有很好地解釋我的問題。我將編輯。 – md5

爲什麼不直接與每行中創建另一個數組的N2（列數）的大小，將其設置爲所有true，然後and每一列。最後，檢查你的新陣列是否只有一個設定位。

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.

來源

2012-11-01 19:22:45

不要將這些位打包成一個整數。相反，請仔細檢查每兩條相鄰的行i和i+1以及總和!(a[i][j]^a[i+1][j])（兩行中位的異或的NOT）。每條線的總和必須恰好爲1。

注意我正在使用邏輯not而不是按位not。我不想得到-1s（這是不是0的按位）。

來源

2012-11-01 19:16:12 zmbq

這是不正確的，如果這些行是相同的（具有零個或更多'真實'），那麼總和將爲零。 – MByD

哦，哦，相反！對！ NOT XOR ... – zmbq

如果我理解正確，您想檢查是否有一列設置爲全部列。然後，只需通過柱和短路檢查柱：

bool is_column_all_ones (const bool *t, size_t col, size_t rows, size_t cols) 
{ 
    for (size_t i = 0; i < rows; i++) { 
     if (!t[i * cols + col]) 
      return false; 
    } 
    return true; 
} 

bool is_one_column_all_ones (const bool *t, size_t rows, size_t cols) 
{ 
    bool found = false; // true if at least one column has been found 
    for (size_t j = 0; j < cols; j++) {   
     if (is_column_all_ones (t, j, rows, cols)) { 
      if (found) { 
       // at least two columns 
       return false; 
      } 
      found = true; 
     } 
    } 
    return found; 
}

來源

2012-11-01 19:19:16

關於散列函數

回答

相關問題