Умножение булевых матриц

Question

Даны две квадратные матрицы n на n типа matrix - A и B

typedef bitset<maxn> t;
typedef array<t, maxn> matrix;

Необходимо найти произведение M = AB

Я пытался сделать так:

matrix matmul(matrix a, matrix b) {
    matrix c;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j])
                c[i] |= b[j];
    return c;
}

И так:

matrix operator*(matrix a, matrix b) {
    matrix C;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; ++j) {
            C[i][j] = 0;
            for (int k = 0; k < n; ++k) 
                C[i][j] = (C[i][j] ^ (a[i][k] & b[k][j]));
        }
    }
    return C;
}

Но оба варианта при перемножении матриц

и

дают

Что, очевидно, не является верным, так как вторая матрица единичная, и поэтому в ответе должна была получиться первая матрица

Подскажите, пожалуйста, правильный алгоритм перемножения или укажите на ошибку в моём коде

UPD: Второй способ был исправлен подобным образом в силу нумерации битов справа налево

matrix operator*(matrix a, matrix b) {
    matrix C;
    for (int i = 0; i < n; i++) {
        for (int j = n-1; j>-1 ; --j) {
            C[i][j] = 0;
            for (int k = 0; k < n; ++k)
                C[i][j] = (C[i][j] ^ (a[i][n-k-1] & b[k][j]));
        }
    }
    return C;
}

Однако, ещё хотелось бы починить первый или узнать другой способ, который записывается компактнее второго или работает быстрее, если это возможно

UPD2: Операции выполняются по модулю 2, то есть 1 + 1 = 0

Answer 1

Умножение элементов заменяется на and, а сложение на or, если в вашем случае эти операции не определены специальным образом

C[i][j] = C[i][j] | (a[i][k] & b[k][j]));

Проверим на Python:

a = [[0,0,1,0,1,0],[1,0,1,0,1,0],[0,1,1,0,1,0],
    [0,1,1,1,1,0],[1,1,0,1,0,0],[1,0,0,0,1,0]]
b = [[1,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],
     [0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,1]]
C =[[0]*6 for _ in range(6)]

for i  in range(6):
    for j  in range(6):
        for k  in range(6):
            C[i][j] = (C[i][j] or (a[i][k] and b[k][j]))
print(C)

[[0, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 0], [0, 1, 1, 0, 1, 0], 
 [0, 1, 1, 1, 1, 0], [1, 1, 0, 1, 0, 0], [1, 0, 0, 0, 1, 0]]

БЛОГ НА HUSL

Умножение булевых матриц

Ответы (1 шт):