Gaussian Elimination GF(2)

// Gaussian elimination over GF(2)
// rows: array of bitmasks representing equations (augmented: last bit is RHS)
function gaussianGF2(rows, n) {
    // n = number of variables
    const basis = [];
    let rank = 0;
    for (let col = n - 1; col >= 0; col--) {
        // Find pivot row with this column bit set
        let pivot = -1;
        for (let r = rank; r < rows.length; r++) {
            if ((rows[r] >> col) & 1) { pivot = r; break; }
        }
        if (pivot === -1) continue; // free variable in this column
        [rows[rank], rows[pivot]] = [rows[pivot], rows[rank]];
        // XOR pivot into all other rows with this bit set
        for (let r = 0; r < rows.length; r++) {
            if (r !== rank && (rows[r] >> col) & 1) rows[r] ^= rows[rank];
        }
        basis[col] = rows[rank];
        rank++;
    }
    return { rank, rows: rows.slice(0, rank) };
}

// Check if target is XOR-reachable from basis vectors
function isReachable(vectors, target) {
    // Insert target into basis; if it reduces to 0, it was already in span
    let x = target;
    for (let i = 29; i >= 0; i--) {
        if (!((x >> i) & 1)) continue;
        const pivot = vectors.find(v => (v >> i) & 1);
        if (!pivot) { vectors.push(x); return false; } // x adds new dimension
        x ^= pivot;
    }
    return true; // x reduces to 0, was in span
}