Everybody knows tic tac toe. We have a 3x3 play field like below, I started counting from 0 for a reason. We'll see that below.

Let us transform the grid to a single line.

For simplicity we look at one player. (the other is completely analogous) If a position in the grid is not occupied, we assign a value of zero (0) to it.

If we place an X in position 2, then we assign a 1 to this position.

So the empty state is 000 000 000 (added spaces for simplicity) Binary is read from right to left.

Let us label the bits (digits in a binary number) in a way similar to the grid.

You may wonder why I reversed the order here. That's because the bit at position i has value 2ⁱ when converting to decimal. That's also the reason why we wrote the indices starting from 0. The rightmost bit is worth 1 in decimal (otherwise we couldn't make odd numbers)

Let me give a quick example of the conversion to decimal with 4 bits (brackets with a subscript denote the base of our number)

(0010)₂ = (0*8 + 0*4 + 1*2 + 0*1)₁₀ = (2)₁₀

(1010)₂ = (1*8 + 0*4 + 1*2 + 0*1)₁₀ = (10)₁₀

So with a certain playfield we can associate a single, unique number.

Let me consider 2 states, one that hasn't got 3-in-a-row and one that has.(both have the same amount of occupied cells)

No winning combo(A)

Winning combo(B)

Okay we now have two examples lets write them in the alternative notation (A) and (B) are the "states" of the board

So it's clear that these are the same as the grids. But we can also guess the close relation to binary strings. Lets do that now. Whenever a cell is occupied with an X we put a 1 in our binary string.

How can we exploit this "notation"? Well we have the winning combo in (B) with cell 2, 4 and 6 occupied. Lets look at the string that has only these cells occupied (call it (W) to signify a winning combo)

The big claim

I claim that we can check if a configuration has 3-in-a-row by using the bitwise AND operation.

Bitwise AND (&) is an operation on 2 strings, "comparing" them one bit at a time. An example

Here we used following properties

• 0 & 0 = 0
• 0 & 1 = 0
• 1 & 0 = 0
• 1 & 1 = 0

Lets see what we get when we use the bitwise AND on (A) and (W)

Now lets see what happens for (B) and (W)

Something magical must have happened.

B & W = W !!!

This is the power of our bitwise operations. You can check that this holds for each winning combination. In our script we can use a test like the following pseudo code

  for(var combo in winningCombos)
    if(currentState & combo === combo)
    "You have won!"