How does the crossover operator work when my output contains only 2 states? I'm currently working on a project where I am using a basic cellular automata and a genetic algorithm to create dungeon-like maps. Currently, I'm having an incredibly hard time understanding how exactly crossover works when my output can only be two states: DEAD or ALIVE (1 or 0).

I understand crossover conceptually - you find two fit members of the population and they exchange genetic material, hopefully producing a fitter offspring. I also understand this is usually done by performing k-point crossover on bit strings (but can also be done with real numbers). 

However, even if I encode my DEAD/ALIVE cells into bits and cross them over, what do I end up with? The cell can only be DEAD or ALIVE. Will the crossover give me some random value that is outside this range?

And even if I were to work on floating-point numbers, wouldn't I just end up with a 1 or 0 anyway? In that case, it seems like it would be better to just randomly mutate DEAD cells into ALIVE cells, or vice versa.

I've read several papers on the topic, but none seem to explain this particular issue (in a language I can understand, anyway). Intuitively, I thought maybe I can perform crossover on a neighbourhood of cells - so I find 2 fit neighbourhoods, and then they exchange members (for example, neighbourhood A gives 4 of its neighbours to neighbourhood B). However, I have not seen this idea anywhere, which leads me to believe it must be fundamentally wrong.

Any help would be greatly appreciated, I'm really stuck on this one.
How do you calculate fitness for your organism if there are only two states? I would think it would be a solution to work on combinations of cells:

If you have blocks of, say, 4x4 cells, then each organism would be encoded using 16 bits. A crossover then is like overlaying two 4x4 blocks, picking the new block from either the first or the second parent. Effectively you are doing this:

0011                   1111                 xx11
0001  combined with    0000  would become   000x
1001                   0000                 x00x
1111                   0000                 xxxx


(this would be a bottom-right corner combined with a top wall segment)

or, as a single bit-string:

0011000110011111 +
1111000000000000 =
xx11000xx00xxxxx


where 'x' can be either 0 or 1, as this is where the two organisms are different.