Operatory bitowe w Brainfuck

13

Twoim zadaniem jest utworzenie jednego programu typu „pieprzenie mózgu” dla każdego z następujących operatorów binarnych. Każdy program powinien pobrać jedną lub dwie liczby 8-bitowe (A i B) z danych wejściowych i obliczyć określoną operację:

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

Nie musisz wdrażać wszystkich 5. Punktacja jest obliczana przez:

#totalCharacters + {4000 * #problemsNotCompleted}

Tak więc prawidłowe wyniki wynoszą od zera (najlepszy) do 20 000 (nic nie ukończone).

Nie dbam o to, gdzie przechowujesz wynik, ani o to, czy zachowujesz dane wejściowe. Załóżmy 8-bitowe komórki i tyle pustych komórek, ile potrzebujesz tylko w prawo.

Możesz założyć, że liczby znajdują się już w dowolnej lokalizacji pamięci, która najbardziej Ci odpowiada, więc nie musisz się martwić operacjami IO.

captncraig
źródło
Czy możemy również rozwiązać zadanie w podobnym minimalistycznym języku, takim jak iot?
FUZxxl,
Nie mam zastrzeżeń do innych języków, o ile nie ma wbudowanych operatorów bitowych.
captncraig,

Odpowiedzi:

7

Wynik: 275

Lepiej jest rozszerzyć je za pomocą licznika binarnego. Mniej intuicyjne części dotyczą możliwości, że A lub B wynosi 0. Nie znalazłem opłacalnego sposobu na zastosowanie nieniszczącej kontroli przepływu w rzeczywistej manipulacji bitami pierwszych trzech. Nawiasem mówiąc, wszystkie powinny działać dobrze z 16-bitowymi komórkami i powoli z 32-bitowymi.

XOR, 86

Zakłada, że ​​A i B znajdują się w komórkach 1 i 2, przechowuje A XOR B w komórce 2, wskaźnik zaczyna się w komórce 0 i kończy w komórce 5.

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

ORAZ 78

Załóżmy, że A i B znajdują się w komórkach 1 i 2, przechowują A OR B w komórce 4, wskaźnik zaczyna się w komórce 0 i kończy w komórce 5.

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

LUB, 86

Załóżmy, że A i B znajdują się w komórkach 1 i 2, przechowują A OR B w komórce 2, wskaźnik zaczyna się w komórce 0 i kończy w komórce 5.

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

ROL, 18

Zakłada, że ​​A znajduje się w komórce 0, przechowuje A ROL 1 w komórce 1, wskaźnik zaczyna się i kończy w komórce 0.

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

NIE 7

Zakłada, że ​​A znajduje się w komórce 0, przechowuje NIE A w komórce 1, wskaźnik zaczyna się i kończy w komórce 0.

+[>-<-]
Daniel Cristofani
źródło
To naprawdę krótkie i całkiem fajne. +1
skopiuj
Poważnie imponujące ulepszenia.
captncraig
8

Wynik: 686

Wszystkie fragmenty zakładają, że liczby są już załadowane do komórek 0 i 1 oraz że wskaźnik wskazuje na komórkę 0. Mogę dodać fragment atoi później, jeśli jest to wymagane do wyzwania. Na razie możesz wypróbować następujący kod:

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


XOR, 221

Wynik jest zapisywany w komórce 10, wskaźnik kończy się w komórce 5

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

ORAZ 209

Wynik jest zapisywany w komórce 10, wskaźnik kończy się w komórce 5

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

LUB 211

Wynik jest zapisywany w komórce 10, wskaźnik kończy się w komórce 5

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

Obróć w lewo, 38

Wynik jest zapisywany w komórce 1, wskaźnik kończy się w komórce 4

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

NIE 7

Wynik jest zapisywany w komórce 1, wskaźnik kończy się na komórce 0

+[+>+<]


Wyjaśnienie:

XOR, AND i OR działają podobnie: Oblicz n / 2 dla każdej liczby i zapamiętaj n mod 2. Oblicz logiczne XOR / AND / OR dla pojedynczych bitów. Jeśli bit wynikowy jest ustawiony, dodaj 2 ^ n do wyniku. Powtórz to 8 razy.

Oto układ pamięci, którego użyłem:

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

  8        9        10
temp  |  temp  |  result

Oto źródło XOR (liczby wskazują, gdzie w tym czasie znajduje się wskaźnik):

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

    <<<
]


W przypadku obracania w lewo ponownie w komórce 2 znajduje się znacznik określający, czy 2n jest równy zero, ponieważ można jedynie ustalić, czy komórka jest niezerowa bezpośrednio. Jeśli tak, bit przeniesienia jest zapisywany w komórce 4, a później dodawany do 2n. Oto układ pamięci:

0      1        2       3       4   
n  |  2n  |  marker  |  0  |  carry 
Kopiuj
źródło
Świetna robota! Zamierzałem, aby każdy program pobierał dane z konsoli, ale im więcej o tym myślę, twój sposób działa dobrze. Nie musisz zmuszać Cię do dodawania ,>,<. Zmienię pytanie.
captncraig,
Chciałbym usłyszeć trochę wyjaśnienia, jak one działają. Wygląda na to, że twoje pierwsze trzy są dość podobne, z wyjątkiem najbardziej wewnętrznej części, ale nie jestem pewien, czy robisz jakieś rozszerzenie binarne (stąd potrzeba 8 komórek), czy też porównujesz krok po kroku, czy jakąś kombinację tych dwóch. Trudno zobaczyć, przechodząc.
captncraig,
@CMP Dodam wyjaśnienie później
skopiuj
3

Wynik (bieżący): 12038 837 / -

Programy zakładają, że liczby są ładowane w dowolnej komórce, określonej ,lub podobnej. Zakłada również, że wszystkie komórki są 8-bitowe bez znaku z zawijaniem w razie potrzeby. Na początku każdego fragmentu numery są ładowane do komórki 0 (i 1, jeśli to konieczne).

Operacje bitowe - 799

Operacje bitowe mają tę samą ogólną 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:

Obróć w lewo A, 1-31 / -

Liczba Ajest ładowana do komórki 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.

NIE A - 7

Liczba Ajest ładowana do komórki 0.

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

+[->-<]
o_o
źródło