Operadores Bitwise em Brainfuck

13

Sua tarefa é criar um programa cerebral para cada um dos seguintes operadores binários. Cada programa deve pegar um ou dois números de 8 bits (A e B) da entrada e calcular a operação especificada:

  1. A XOR B
  2. A AND B
  3. A OR B
  4. A Shifted Left by 1 (circular shift)
  5. NOT A

Você não precisa implementar todos os 5. A pontuação é calculada por:

#totalCharacters + {4000 * #problemsNotCompleted}

Portanto, as pontuações válidas variam de zero (melhor) a 20.000 (nada concluído).

Não me importo onde você armazena o resultado ou se preserva ou não a entrada. Suponha células de 8 bits e quantas células vazias forem necessárias apenas para a direita.

Você pode supor que os números já estejam em qualquer local de memória que funcione melhor para você, para que você não precise se preocupar com operações de E / S.

captncraig
fonte
Também podemos resolver a tarefa em uma linguagem minimalista semelhante, como iot?
FUZxxl
Não tenho objeções a nenhum outro idioma, desde que não haja operadores de bits em bits.
Captncraig 11/12/12

Respostas:

7

Pontuação: 275

Funciona melhor para expandi-los com um contador binário. As partes menos intuitivas lidam com a possibilidade de que A ou B seja 0. Não encontrei uma maneira lucrativa de usar o controle não destrutivo do fluxo na manipulação real de bits dos três primeiros. Aliás, todos eles devem funcionar bem com células de 16 bits e lentamente com 32 bits.

XOR, 86

Supõe que A e B estão nas células 1 e 2, armazena A XOR B na célula 2, o ponteiro começa na célula 0 e termina na célula 5.

-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>-<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

AND, 78

Supõe que A e B estão nas células 1 e 2, armazena A ou B na célula 4, o ponteiro começa na célula 0 e termina na célula 5.

-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>[<<<<+>>>>-]<-]>+>]<[<[<<<++>>>-]<<]]

OU 86

Supõe que A e B estão nas células 1 e 2, armazena A ou B na célula 2, o ponteiro começa na célula 0 e termina na célula 5.

-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>+<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

ROL, 18

Supõe que A esteja na célula 0, armazena um ROL 1 na célula 1, o ponteiro inicia e termina na célula 0.

[>++[>>]<[>+>]<<-]

NÃO 7

Supõe que A esteja na célula 0, armazena NÃO A na célula 1, o ponteiro inicia e termina na célula 0.

+[>-<-]
Daniel Cristofani
fonte
Isso é muito curto e muito legal. +1
copie
Melhorias seriamente impressionantes.
Captncraig 19/11/2013
8

Pontuação: 686

Todos os trechos assumem que os números já estão carregados nas células 0 e 1 e que o ponteiro aponta para a célula 0. Posso adicionar um trecho de atoi posteriormente, se necessário para o desafio. Por enquanto, você pode tentar o código assim:

+++++++++>    number 1
++++<         number 2


XOR, 221

O resultado é gravado na célula 10, o ponteiro termina na célula 5

>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->>+<<]>[>[-<->]<[->+<]]>[[-]<<<[->+>-<<
]>[-<+>]+>+++++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

AND, 209

O resultado é gravado na célula 10, o ponteiro termina na célula 5

>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->[->+<]<]>[-]>[-<<<[->+>-<<]>[-<+>]+>++
+++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

OR, 211

O resultado é gravado na célula 10, o ponteiro termina na célula 5

>>>>>++++++++[-<<<<<[->>+<<[->>->+<]>>[->>>>+<<]<<<<]>>>[-<<<+>>>]<<[->+<[->->+>
>>>>]>[->>>>>+>>]<<<<<<<<]>>[-<<+>>]>>>[->>+<<]>[->+<]>[[-]<<<[->+>-<<]>[-<+>]+>
+++++++[-<[->>++<<]>>[-<<+>>]<]<[->>>>+<<<<]>>]<<<]

Girar para a esquerda, 38

O resultado é gravado na célula 1, o ponteiro termina na célula 4

[->++>+<[>-]>[->>+<]<<<]>>>>[-<<<+>>>]

NÃO 7

O resultado é gravado na célula 1, o ponteiro termina na célula 0

+[+>+<]


Explicação:

XOR, AND e OR funcionam de maneira semelhante: calcule n / 2 para cada número e lembre-se do mod 2. Calcule o XOR / AND / OR lógico para os bits únicos. Se o bit resultante estiver definido, adicione 2 ^ n ao resultado. Repita isso 8 vezes.

Este é o layout de memória que eu usei:

 0      1        2        3      4        5         6        7
n1  |  n2  |  marker  |  n/2  |  0  |  counter  |  bit1  |  bit2  |

  8        9        10
temp  |  temp  |  result

Aqui está a fonte do XOR (os números indicam onde o ponteiro está naquele momento):

>>>>>
++++ ++++ counter
[
    -
    <<<<<

    divide n1 by two
    [ 0 
        -
        >>+ set marker 2
        << 0
        [->>->+<] dec marker inc n/2
        >> 2 or 4
        [->>>>+<<] 
        <<<<
    ]
    >>>
    [-<<<+>>>]
    <<

    divide n2 by two
    [ 1
        -
        >+ set marker 2
        < 1
        [->->+>>>>>] dec marker inc n/2
        > 2 or 9
        [->>>>>+>>]
        <<<< <<<< 
    ]
    >>[-<<+>>] 3

    >>> 6

    [->>+<<]>[>[-<->]<[->+<]]>  one bit xor 8

    [
        [-]<<< 5
        [->+>-<<] copy counter negative
        > 6
        [-<+>]
        +> 7
        ++++ +++  cell 6 contains a one and cell 7 how many bits to shift
        [-<[->>++<<]>>[-<<+>>]<]  2^n
        < 6
        [->>>>+<<<<]
        >> 8
    ]

    <<<
]


Para rotação à esquerda, mais uma vez há um marcador na célula 2 para determinar se 2n é zero, pois você só pode determinar se uma célula é diferente de zero diretamente. Nesse caso, um bit de transporte é gravado na célula 4 e posteriormente adicionado a 2n. Este é o layout da memória:

0      1        2       3       4   
n  |  2n  |  marker  |  0  |  carry 
cópia de
fonte
Ótimo trabalho! Eu pretendia que cada programa recebesse informações do console, mas quanto mais penso nisso, seu caminho funciona bem. Não há necessidade de fazer você adicionar,>,< . Vou editar a pergunta.
Captncraig 11/12/12
Gostaria de ouvir uma explicação de como elas estão funcionando. Parece que seus três primeiros são bem parecidos, exceto a parte mais interna, mas não tenho certeza se você está fazendo algum tipo de expansão binária (portanto, são necessárias 8 células), ou uma comparação pouco a pouco, ou alguma combinação das duas. Difícil de enxergar.
Captncraig 11/12/12
@CMP Adicionarei uma explicação mais tarde
copie
3

Pontuação (atual): 12038837 / -

Os programas assumem que os números são carregados em qualquer célula especificada, por ,ou similar. Ele também pressupõe que todas as células tenham 8 bits sem assinatura com quebra automática, conforme necessário. No início de cada trecho, os números são carregados na célula 0 (e 1, se necessário).

Operações de bit - 799

As operações de bit seguem a mesma estrutura geral.

Firstly, we define a divmod 2 (DM2) function.
CELLS:   A  B   C  D
INPUT:  *A  0   0  0
OUTPUT: *0 A/2 A%2 0
dp@A; while{
  dec A,2; inc B,1; dp@A; inc A,1
  while{ #Check if A was 1 at the start
    dec D,1; pour A,C; dp@A;
  }
  dec C,1; pour C,A; inc D,1; dp@D
  #If A was 1 at the start, D will be 1 here
  while{ 
    dec D,1; inc C,1; dec B,1; dp@D
  }
  dp@A
}
Translated into BF, we have
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]
I'm not that good at BF, so my algorithm may not be the smallest.

Next, we define the program.
In this, we assume that the numbers are loaded in $2 (cell 2) and $3.

inc $1,8; dp@1 {
  dec  $1
  pour $3,$6
  DM2  $2        # result in $3,$4
  DM2  $6        # result in $7,$8
  pour $7, $2
  pour $8,$5
  bop  $4,$5     # result in $6
  pour $1,$5
  pour $5,$4,$1
  down $4,$5     # decrease $4 till 0, decrease $5 by same amount
  inc  $5,#7
  shl  $6,$5
  pour $6,$0     # $0 is result
  dp@  1
}
#Now, the result is in $0

Translated to BF (with linebreaks for readability):
  >++++++++[
    ->>[->>>+<<<]<
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]>>>>  #DM2 $2
    [->+<[>>>-<<<[->>+<<]]>>-[<<+>>-]>+[-<+<->>]<<<]>     #DM2 $6
    [-<<<<<+>>>>>]>
    [-<<<+>>>]<<<<
    (bop)<<<
    [->>>>+<<<<]>>>>
    [<+<<<+>>>>-]<
    [->-<]>
    +++++++
    [->[-<<++>>]<<[->>+<<]>]
    [-<<<<<<+>>>>>>]
    <<<<<
  ]

Replace (bop) by the appropriate expression.

XOR works like this: (252-5+15=262)
  [->-<]>[[-]>+<]
AND works like this: (252-5+11=258)
  [>[>+<-]<-]
OR  works like this: (252-5+32=279)
  [->>>+<<<]>[->>+<<]>>[[-]<+>]<<<

So, combining these, we have a total of 262+258+279=799 D:

Gire à esquerda A, 1 - 31 / -

O número Aé carregado na célula 0.

Pseudocode
    $0 := A
    $1 := $0 << 1    # this has the effect of discarding the top bit of A
    $2 := $0
    $3 := $0 << 1
    $2 -= $1 >> 1    # $2 now contains the top bit of A
    if $2 then $3++  # $3 now contains A rotated left 1
    res:= $3         # the result is in cell 3 now

Real code
    [->++>+>++<<<]>[-->-<]>[>+<[-]]
If you don't always need the pointer in the same position,
substitute [>+>] for the last loop (3 less chars).
However, the pointer will then sometimes end up in position 2, sometimes in position 4.

NÃO A - 7

O número Aé carregado na célula 0.

Pseudocode
    $0  := A
    $0  += 1
    $1  := 256-$0   #since ~A=255-A
    res := $1

+[->-<]
o_o
fonte