I am asking if it is possible to improve *considerably* integer matrix multiplication with [bitwise operations](https://stackoverflow.com/questions/276706/what-are-bitwise-operators). The matrices are small, and the elements are small nonnegative integers (small means at most 20).

To keep us focused, let's be extremely specific, and say that I have two 3x3 matrices, with integer entries 0<=x<15.

The following naive C++ implementation executed a million times performs around 1s, measured with linux `time`.

```
#include <random>

int main() {
//Random number generator
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(0, 15);

int A[3][3];
int B[3][3];
int C[3][3];
for (int trials = 0; trials <= 1000000; trials++) {
    //Set up A[] and B[]
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            A[i][j] = distr(eng);
            B[i][j] = distr(eng);
            C[i][j] = 0;
        }
    }
    //Compute C[]=A[]*B[]
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }
}
return 0;
}

```

Notes:

1. The matrices are not necessarily sparse.
2. [Strassen-like](https://stackoverflow.com/questions/1920031/strassens-algorithm-for-matrix-multiplication) comments does not help here.
3. Let's try not to use the *circumstantial* observation, that in this *specific problem* the matrices `A[]` and `B[]` can be encoded as a **single** 64 bit integer. Think of what would happen for just a bit larger matrices.
4. Computation is single-threaded.

---

Related: [Binary matrix multiplication bit twiddling hack](https://stackoverflow.com/questions/18447321/binary-matrix-multiplication-bit-twiddling-hack) and [What is the optimal algorithm for the game 2048?](https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048)