A r*c grid has only 0's ans 1's . In each iteration , if there is any adjacent cell (up,down,left,right) same to it, the value of the current cell will be flipped . Now , how to come up with a bitwise formula to do this . It can be done with a simple if condition , but I want to know the bitwise operation to do this so the whole operation can be done once per row .
I am talking about this problem . I saw a solution using this concept here . But I couldn't understand how this is used to do the determine the cell value by this XOR operations.
ans[i] ^= ((l ^ r) | (r ^ u) | (u ^ d)) | (~s[i] ^ l);
ans[i] &= prefix;
Any help would be appreciated :D
For the start, consider s[i], l, r, u, and d to be single bits, that is, boolean variables.
s[i] (abbreviated as s in this answer) is the old color of the cell to be updated. l, r, u, and d are the colors of the adjacent cells left, right, above (up), and below (down) of the cell to be updated.ans[i] (abbreviated as ans in this answer) is the new color of the cell after the update.ans = s and update it only if needed.Recall the rules from the game for a single cell C:
For the first condition you can use a fail-fast approach. No matter the color of C, if the adjacent cells have various colors (some are 0 and some are 1) then C changes its color. To check whether the adjacent cells l, r, u, and d have various colors you only need three checks ✱:
various_adjacent_colors = (l != r) || (r != u) || (u != d)
In bit-wise notation this is
various_adjacent_colors = (l ^ r) | (r ^ u) | (u ^ d)
✱ The "missing" checks like r != d are not necessary. Think about it the other way: If all three checks fail, then we know (l == r) && (r == u) && (u == d). In that case, from transitivity of == follows that (l == u), and (l == d), and (r == d). Therefore, all colors are the same.
If we find various adjacent colors, then we change s:
if (various_adjacent_colors)
ans = !s
In bit-wise notation this is
ans ^= various_adjacent_colors
If we did not fail-fast, we know that all adjacent colors are equal to each other but not if they are equal to s. If s == all_adjacent_colors then we change s and if s != all_adjacent_colors then we retain s.
if (!various_adjacent_colors && s == l) // l can be replaced by either r, u, or d
ans = !s
In bit-wise notation this is
ans ^= ~various_adjacent_colors & ~(s ^ l) or
ans ^= ~various_adjacent_colors & (~s ^ l)
Now let's inline (and slightly simplify) all the bit-wise notations:
vari = (l ^ r) | (r ^ u) | (u ^ d); ans ^= vari; ans ^= ~vari & (~s ^ l) is the same as
vari = (l ^ r) | (r ^ u) | (u ^ d); ans ^= vari | (~s ^ l) is the same as
ans ^= ((l ^ r) | (r ^ u) | (u ^ d)) | (~s ^ l)
Seems familiar, right? :)
So far, we only considered single bits. The linked solution uses bit-vectors instead to simultaneously update all bits/cells in a row of the 2D game board. This approach only fails at the borders of the game board:
From r = s[i] << 1 the game board might end up bigger than it should be. ans[i] &= prefix fixes the size by masking overhanging bits.
At the top and bottom row the update does not work because u = s[i-1] and d = s[i+i] do not exist. The author updates these rows "manually" in a for loop.
The update for the leftmost and rightmost cell in each row might be wrong since r = s[i] << 1 and l = s[i] >> 1 shift in "adjacent" cells of color 0 which are not actually in the game. The author updates these cells "manually" in another for loop.
By the way: A (better?) alternative to the mentioned "manual" border updates is to slightly enlarge the game board with an additional virtual row/column at each border. Before each game iteration, the virtual rows/columns are initialized such that they don't affect the update. Then the update of the actual game board is done as usual. The virtual rows/columns don't have to be stored, instead use ...
// define once for the game
bitset<N> maskMsb, maskLsb;
maskMsb[m-1] = 1;
maskLsb[0] = 1;
// define for each row when updating the game board
bitset<N> l = (s[i] >> 1) | (~s[i] & maskMsb);
bitset<N> r = (s[i] << 1) | (~s[i] & maskLsb);
bitset<N> u = i+1 <= n-1 ? s[i+1] : ~s[n-1];
bitset<N> d = i-1 >= 0 ? s[i-1] : ~s[0];