89 lines
1.9 KiB
C++
89 lines
1.9 KiB
C++
#include <bitset>
|
|
#include <iostream>
|
|
#include <cstdint>
|
|
#include "matrix.h"
|
|
|
|
namespace splat {
|
|
template <int S>
|
|
std::bitset<S>& matrix<S>::operator[](int i){
|
|
return bits[i];
|
|
}
|
|
|
|
template <int S>
|
|
const std::bitset<S>& matrix<S>::operator[](int i) const {
|
|
return bits[i];
|
|
}
|
|
|
|
|
|
template <int S>
|
|
const bool matrix<S>::get(int row, int column) const {
|
|
return bits[row][S-column-1];
|
|
}
|
|
|
|
|
|
template <int S>
|
|
void matrix<S>::debug() {
|
|
for(int i=0; i<S; i++){
|
|
for(int ii=0; ii<S; ii++){
|
|
std::cout << get(i,ii);
|
|
}
|
|
std::cout << "\n";
|
|
}
|
|
}
|
|
|
|
|
|
template <int S>
|
|
void gaussianElimination(matrix<S>& matrix){
|
|
int top = 0;
|
|
for(int column=0; column<S; column++){
|
|
// get the position of the first one (pivot)
|
|
int firstOnePosition = -1;
|
|
for(int row=top; row<S; row++){
|
|
if(matrix.get(row, column)){
|
|
firstOnePosition = row;
|
|
break;
|
|
}
|
|
}
|
|
|
|
// if there was no one, we move on
|
|
if(firstOnePosition==-1){
|
|
//top++;
|
|
continue;
|
|
}
|
|
|
|
// now swap the pivot row with the relative top row
|
|
if(firstOnePosition!=top){
|
|
std::bitset<S> temp = matrix[top];
|
|
matrix[top] = matrix[firstOnePosition];
|
|
matrix[firstOnePosition] = temp;
|
|
}
|
|
|
|
// now we XOR all the rows below our pivot with the pivot row
|
|
for(int row = firstOnePosition+1; row<S; row++){
|
|
if(matrix.get(row,column)){
|
|
matrix[row]^=matrix[top];
|
|
}
|
|
}
|
|
top++;
|
|
}
|
|
}
|
|
|
|
template <int S>
|
|
int getRank(matrix<S>& matrix){
|
|
gaussianElimination(matrix);
|
|
int rank = 0;
|
|
for(int i=0; i<S; i++){
|
|
if(matrix[i]!=std::bitset<S>(0)){
|
|
rank++;
|
|
}
|
|
}
|
|
return rank;
|
|
}
|
|
|
|
|
|
template void matrix<10>::debug();
|
|
template int getRank<3>(matrix<3>&);
|
|
template int getRank<32>(matrix<32>&);
|
|
template int getRank<10>(matrix<10>&);
|
|
}
|