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 N
2 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
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…