Helps with understanding cellular automaton code

Question

I would like you to help me understand a code for calculating and presenting cellular automata that I found on the Internet. The code in question is as follows::

#include <stdio.h>
#include <stdlib.h>
void PrintfVetor(char vetor[], char tamanho);
void CopiaVetor(char vetor_in[], char vetor_out[], int tamanho);

int main(int argc, char* argv[])
{
    char *L_ant, *L_atu;
    int n, k, bit;
    int N, linhas, regra;
/* Obtem dados de entrada */
    printf("Digite o comprimento da linha: ");
    scanf("%d", &N);
    printf("Digite o numero de linhas: ");
    scanf("%d", &linhas);
    printf("Digite a regra a ser utilizada (0 a 255): ");
    scanf("%d", &regra);
/* Aloca espaco para o vetor atual e o anterior */     
    L_ant = (char*) malloc(N*sizeof(char));
    L_atu = (char*) malloc(N*sizeof(char));
/* Criacao da linha inicial */
/* Preenche a linha inicial com zeros */
    for(n=0; n<N; n++)
            L_ant[n] = 0;
/* Insere o valor 1 na posicao do meio da linha inicial */
    L_ant[N/2] = 1;
/* Define que na linha atual, a primeira posicao e a ultima serao sempre 
iguais a 0 */
    L_atu[0] = L_atu[N-1] = 0;
/* Escreve a linha inicial na tela */
    PrintfVetor(L_ant, N);
/* Percorre as próximas linhas */
    for(k=2; k<=linhas; k++)
    {
/* Percorre cada posicao da linha atual, exceto a primeira e a ultima 
posicoes */
            for(n=1; n<N-1; n++)
            {
                    /* Obtem a regra para a posicao atual, e atualiza essa 
posicao na linha atual */
                    bit = L_ant[n-1]*4+L_ant[n]*2+L_ant[n+1];
                    L_atu[n] = (regra&(1<<bit))!=0;
            }
/* Escreve a linha atual na tela */
            PrintfVetor(L_ant, N);
/* Atualiza a linha anterior */
            CopiaVetor(L_atu, L_ant, N);
    }
/* Libera a memoria dinamica das linhas */
    free(L_ant);
    free(L_atu);
    return 0;
}

void PrintfVetor(char vetor[], char tamanho)
{
    int n;
    for(n=0; n<tamanho; n++)
            printf("%d ", vetor[n]);
    puts("");
}

void CopiaVetor(char vetor_in[], char vetor_out[], int tamanho)
{
    int n;
    for(n=0; n<tamanho; n++)
            vetor_out[n] = vetor_in[n];
}`

The program itself I understood, but I can’t understand the calculation that is done in this part here:

bit = L_ant[n-1]*4+L_ant[n]*2+L_ant[n+1];
L_atu[n] = (regra&(1<<bit))!=0;

If you could explain to me, I would be most grateful.

code taken from the blog: http://progcmaismais.blogspot.com/2011/01/codigo-em-c-automatos-celulares.html

Answer 1

It bit by bit encoded the "neighbors".

In bit 2 (value 4), placed neighbor on the left:

4*L_ant[n-1]

In bit 1 (value 2), put the current value:

2*L_ant[n]

Already in bit 0 (value 1), put the neighbor on the right:

L_ant[n+1]

Thus, if obtained 6 = 110, we know that the living neighbors are the one of the current position and the one of the right.

I, particularly, since you’re only doing bit operations, would stay in them:

 bit = L_ant[n-1]<<2 | L_ant[n]<<1 | L_ant[n+1]

After getting that number, he does 2^bit through the bit displacement: 1<<bit. Therefore, the previous number 6 would be transformed into 64 after this operation.

Do regra & (1<<bit) is to ask whether, within the information read in regra, one of them matches the layout of the neighborhood. For example, if I provide regra == 192, there would be match for my 64. But this is no longer true with regra == 180, since it does not even contain 64.

The assignment in L_atu[n] indicates that the regra works to know if the index element n will remain alive in the next round.

It does the assignment as follows to ensure that the value in L_atu[n] whether 1 or 0:

L_atu[n] = (regra & (1<<bit)) != 0

If I didn’t have that != 0, would be stored in L_atu[n] the value 1<<bit, provided that this value is within regra.