Improve nested loop efficiency and enter the xor value of the index row times the index of the column into an array using the nested loop?

It is possible to optimize slightly population of the 2D array taking into account that XOR is a commutative operation, that is x ^ y == y ^ x.

Thus for the “square” part of the array (while i and j are below N = Math.min(m, n)), a “triangle” part should be considered excluding the main diagonal which will be populated with 0 (because x ^ x == 0). So instead of N2 operations it will take N * (N - 1) / 2 operations.

For the remaining part (over min) the XOR results should be calculated as before.

int min;
int max;
boolean moreRows;

if (m > n) {
    min = n;
    max = m;
    moreRows = true;
} else {
    min = m;
    moreRows = false;
    max = n;
}
int sum = 0;
int[][] ar2 = new int[m][n];
// square part
for (int i = 0; i < min; i++) {
    for (int j = 0; j < i; j++) {
        int t = i ^ j;
        ar2[i][j] = ar2[j][i] = t;
        sum += 2 * t;
    }
}
for (int i = min; i < max; i++) {
    for (int j = 0; j < min; j++) {
        int t = i ^ j;
        sum += t;
        if (moreRows) {
            ar2[i][j] = t;
        } else {
            ar2[j][i] = t;
        }
    }
}
for (int[] row: ar2) {
    System.out.println(Arrays.toString(row));
}

System.out.println("sum: " + sum);

Output for m = 5, n = 8:

[0, 1, 2, 3, 4, 5, 6, 7]
[1, 0, 3, 2, 5, 4, 7, 6]
[2, 3, 0, 1, 6, 7, 4, 5]
[3, 2, 1, 0, 7, 6, 5, 4]
[4, 5, 6, 7, 0, 1, 2, 3]
sum: 140

Leave a Comment