Search code examples
bit-manipulationbitboard

Is there a cheap way to "mirror" the bits in a byte?

When trying to test for reachability on a straight line without looping, you can use Bitboard representation. Imagine chess, a row or column of the board represented as a byte and the question if a Rook on square X can capture a target on square T.

Let T: Target, X: Start, O: other occupied squares, _: empty square

I found it convenient to visualize the possible scenarios, using those symbols:

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

There are 4 cases of interest here - labeled from A-D. Cases A and B are easy to handle.

But cases C and D are not. You cannot simply test for > or < to find out if the target is reachable or if the path is blocked.

What one could do, though is to transform C,D to A,B by mirroring the bits in the byte. So Bit 0 -> Bit 7, Bit 1 -> Bit 6, ...

Does anyone know if there is an optimized implementation for doing that flipping?

EDIT: I just noticed that another case is: E: OT__X___ ... my theory goes bad, yet the question remains. :)

Solution

  • Instead of 

    // __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

    It Seems logical to reverse X and T in cases C and D:

    //C: __OTO_X_ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//D: __OOT_X_ -> Target left of X, X leftmost    -> T > X and O < X -> reachable

    I realize that if T was a bishop and X was a Rook, that T may not move the way X can, but all we're doing is seeing if T was a Rook if it could move to X. Answering that question is the same as X moving to T. Either it can or it can't which answers the opposite (can X move to T).