Bitweise Operatoren in Brainfuck

13

Ihre Aufgabe ist es, ein Brainfuck-Programm für jeden der folgenden Binäroperatoren zu erstellen. Jedes Programm sollte eine oder zwei 8-Bit-Zahlen (A und B) von der Eingabe nehmen und die angegebene Operation berechnen:

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

Sie müssen nicht alle 5 implementieren. Die Bewertung wird berechnet durch:

#totalCharacters + {4000 * #problemsNotCompleted}

Gültige Werte liegen also zwischen null (am besten) und 20.000 (nichts abgeschlossen).

Es ist mir egal, wo Sie das Ergebnis speichern oder ob Sie die Eingabe beibehalten. Nehmen Sie 8-Bit-Zellen und so viele leere Zellen an, wie Sie nur rechts benötigen.

Sie können davon ausgehen, dass sich die Nummern bereits in dem Speicher befinden, der für Sie am besten geeignet ist, sodass Sie sich nicht um E / A-Vorgänge kümmern müssen.

captncraig
quelle
Können wir die Aufgabe auch in einer ähnlichen minimalistischen Sprache wie iot lösen?
FUZxxl
Ich habe keine Einwände gegen andere Sprachen, solange es keine eingebauten bitweisen Operatoren gibt.
Captncraig

Antworten:

7

Ergebnis: 275

Es ist besser, diese mit einem Binärzähler zu erweitern. Die weniger intuitiven Teile befassen sich mit der Möglichkeit, dass A oder B 0 ist. Ich habe keinen rentablen Weg gefunden, die zerstörungsfreie Flusssteuerung bei der tatsächlichen Bitmanipulation der ersten drei zu verwenden. Übrigens sollten alle mit 16-Bit-Zellen und langsam mit 32-Bit funktionieren.

XOR, 86

Angenommen, A und B befinden sich in den Zellen 1 und 2, speichern A XOR B in Zelle 2, der Zeiger beginnt in Zelle 0 und endet in Zelle 5.

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

UND, 78

Angenommen, A und B befinden sich in den Zellen 1 und 2, speichern A ODER B in Zelle 4, der Zeiger beginnt in Zelle 0 und endet in Zelle 5.

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

ODER 86

Angenommen, A und B befinden sich in den Zellen 1 und 2, speichern A ODER B in Zelle 2, der Zeiger beginnt in Zelle 0 und endet in Zelle 5.

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

ROL, 18

Angenommen, A befindet sich in Zelle 0, speichert A ROL 1 in Zelle 1, der Zeiger beginnt und endet in Zelle 0.

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

NICHT, 7

Angenommen, A befindet sich in Zelle 0, speichert NOT A in Zelle 1, der Zeiger beginnt und endet in Zelle 0.

+[>-<-]
Daniel Cristofani
quelle
Das ist wirklich kurz und ziemlich cool. +1
Kopie
Ernsthaft beeindruckende Verbesserungen.
Captncraig
8

Ergebnis: 686

Alle Snippets setzen voraus, dass die Zahlen bereits in Zelle 0 und 1 geladen sind und der Zeiger auf Zelle 0 zeigt. Ich kann später ein Atoi-Snippet hinzufügen, wenn dies für die Herausforderung erforderlich ist. Im Moment können Sie den Code folgendermaßen ausprobieren:

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


XOR 221

Das Ergebnis wird in Zelle 10 geschrieben, der Zeiger endet in Zelle 5

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

UND, 209

Das Ergebnis wird in Zelle 10 geschrieben, der Zeiger endet in Zelle 5

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

ODER 211

Das Ergebnis wird in Zelle 10 geschrieben, der Zeiger endet in Zelle 5

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

Nach links drehen, 38

Ergebnis wird in Zelle 1 geschrieben, Zeiger endet in Zelle 4

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

NICHT, 7

Ergebnis wird in Zelle 1 geschrieben, Zeiger endet in Zelle 0

+[+>+<]


Erläuterung:

XOR, AND und OR funktionieren alle auf ähnliche Weise: Berechnen Sie n / 2 für jede Zahl und merken Sie sich n mod 2. Berechnen Sie das logische XOR / AND / OR für die einzelnen Bits. Wenn das resultierende Bit gesetzt ist, addieren Sie 2 ^ n zum Ergebnis. Wiederholen Sie das 8 Mal.

Dies ist das Speicherlayout, das ich verwendet habe:

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

  8        9        10
temp  |  temp  |  result

Hier ist die Quelle für XOR (Zahlen geben an, wo sich der Zeiger zu diesem Zeitpunkt befindet):

>>>>>
++++ ++++ 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
    ]

    <<<
]


Beim Drehen nach links befindet sich erneut eine Markierung in Zelle 2, um zu bestimmen, ob 2n Null ist, da Sie nur direkt bestimmen können, ob eine Zelle nicht Null ist. Wenn ja, wird ein Übertragsbit in Zelle 4 geschrieben und später zu 2n addiert. Dies ist das Speicherlayout:

0      1        2       3       4   
n  |  2n  |  marker  |  0  |  carry 
Kopieren
quelle
Gute Arbeit! Ich hatte vor, dass jedes Programm Eingaben von der Konsole übernimmt, aber je mehr ich darüber nachdenke, desto besser funktioniert Ihr Weg. Sie müssen nicht hinzufügen ,>,<. Ich werde Frage bearbeiten.
Captncraig
Es würde mich interessieren, eine Erklärung dafür zu hören, wie diese funktionieren. Es sieht so aus, als ob Ihre ersten drei ziemlich ähnlich sind, mit Ausnahme des innersten Teils, aber ich bin mir nicht sicher, ob Sie eine Art binäre Erweiterung durchführen (daher werden 8 Zellen benötigt) oder nach und nach vergleichen oder eine Kombination der beiden. Schwer zu erkennen, wenn man durchgeht.
Captncraig
@CMP Ich werde später eine Erklärung hinzufügen
kopiere den
3

Ergebnis (aktuell): 12038 837 / -

Die Programme gehen davon aus, dass Zahlen in eine Zelle geladen werden, die von ,oder ähnlich angegeben wurde. Es wird außerdem davon ausgegangen, dass alle Zellen 8-Bit-Zellen ohne Vorzeichen sind und nach Bedarf umbrochen werden. Zu Beginn jedes Snippets werden die Zahlen in Zelle 0 (und bei Bedarf in Zelle 1) geladen.

Bitoperationen - 799

Die Bitoperationen folgen der gleichen allgemeinen Struktur.

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:

Nach links drehen A, 1 - 31 / -

Die Nummer Awird in Zelle 0 geladen.

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.

NICHT A - 7

Die Nummer Awird in Zelle 0 geladen.

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

+[->-<]
o_o
quelle