Operadores Bitwise en Brainfuck

13

Su tarea es crear un programa de brainfuck para cada uno de los siguientes operadores binarios. Cada programa debe tomar uno o dos números de 8 bits (A y B) de la entrada y calcular la operación especificada:

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

No tiene que implementar todos los 5. La puntuación se calcula mediante:

#totalCharacters + {4000 * #problemsNotCompleted}

Por lo tanto, los puntajes válidos son de cero (mejor) a 20,000 (nada completado).

No me importa dónde almacene el resultado, o si conserva o no la entrada. Asuma las celdas de 8 bits y todas las celdas vacías que necesite a la derecha solamente.

Puede suponer que los números ya están en cualquier ubicación de memoria que funcione mejor para usted, por lo que no necesita preocuparse por las operaciones de E / S.

captncraig
fuente
¿Podemos resolver también la tarea en un lenguaje minimalista similar como iot?
FUZxxl
No tengo objeciones a ningún otro idioma, siempre que no haya operadores bit a bit incorporados.
captncraig

Respuestas:

7

Puntuación: 275

Funciona mejor expandirlos con un contador binario. Las partes menos intuitivas tratan con la posibilidad de que A o B sea 0. No encontré una forma rentable de usar el control de flujo no destructivo en la manipulación de bits real de los primeros tres. Por cierto, todo esto debería funcionar bien con celdas de 16 bits y lentamente con 32 bits.

XOR, 86

Asume que A y B están en las celdas 1 y 2, almacena A XOR B en la celda 2, el puntero comienza en la celda 0 y termina en la celda 5.

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

Y 78

Asume que A y B están en las celdas 1 y 2, almacena A o B en la celda 4, el puntero comienza en la celda 0 y termina en la celda 5.

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

O, 86

Asume que A y B están en las celdas 1 y 2, almacena A o B en la celda 2, el puntero comienza en la celda 0 y termina en la celda 5.

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

ROL, 18

Asume que A está en la celda 0, almacena A ROL 1 en la celda 1, el puntero comienza y termina en la celda 0.

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

NO 7

Asume que A está en la celda 0, almacena NO A en la celda 1, el puntero comienza y termina en la celda 0.

+[>-<-]
Daniel Cristofani
fuente
Eso es muy corto y genial. +1
copia el
Mejoras realmente impresionantes.
Captncraig
8

Puntuación: 686

Todos los fragmentos suponen que los números ya están cargados en la celda 0 y 1 y que el puntero apunta a la celda 0. Puedo agregar un fragmento atoi más adelante si es necesario para el desafío. Por ahora, puedes probar el código de esta manera:

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


XOR, 221

El resultado se escribe en la celda 10, el puntero termina en la celda 5

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

Y, 209

El resultado se escribe en la celda 10, el puntero termina en la celda 5

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

O 211

El resultado se escribe en la celda 10, el puntero termina en la celda 5

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

Girar a la izquierda, 38

El resultado se escribe en la celda 1, el puntero termina en la celda 4

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

NO 7

El resultado se escribe en la celda 1, el puntero termina en la celda 0

+[+>+<]


Explicación:

XOR, AND y OR funcionan de manera similar: calcule n / 2 para cada número y recuerde n mod 2. Calcule el XOR / AND / OR lógico para los bits individuales. Si se establece el bit resultante, agregue 2 ^ n al resultado. Repite eso 8 veces.

Este es el diseño de memoria que utilicé:

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

  8        9        10
temp  |  temp  |  result

Aquí está la fuente de XOR (los números indican dónde está el puntero en ese 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 girar a la izquierda, una vez más hay un marcador en la celda 2 para determinar si 2n es cero, ya que solo puede determinar si una celda no es cero directamente. Si es así, se escribe un bit de acarreo en la celda 4 y luego se agrega a 2n. Este es el diseño de la memoria:

0      1        2       3       4   
n  |  2n  |  marker  |  0  |  carry 
Copiar
fuente
¡Buen trabajo! Tenía la intención de que cada programa recibiera información de la consola, pero cuanto más lo pienso, su forma funciona bien. No hay necesidad de hacerte agregar ,>,<. Editaré la pregunta.
captncraig
Me interesaría escuchar un poco de explicación sobre cómo funcionan. Parece que sus tres primeros son bastante similares, excepto por la parte más interna, pero no estoy seguro de si está haciendo algún tipo de expansión binaria (por lo tanto, se necesitan 8 celdas), o una comparación poco a poco, o alguna combinación de los dos. Difícil de ver al pasar.
captncraig
@CMP Agregaré una explicación más tarde
copia el
3

Puntuación (actual): 12038837 / -

Los programas suponen que los números se cargan en cualquier celda especificada, por ,o similar. También supone que todas las celdas son de 8 bits sin firmar con ajuste según sea necesario. Al comienzo de cada fragmento, los números se cargan en la celda 0 (y 1 si es necesario).

Operaciones de bits - 799

Las operaciones de bit siguen la misma estructura general.

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:

Girar a la izquierda A, 1-31 / -

El número Ase carga en la celda 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.

NO A - 7

El número Ase carga en la celda 0.

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

+[->-<]
o_o
fuente