Operator Bitwise di Brainfuck

13

Tugas Anda adalah membuat satu program brainfuck untuk masing-masing operator biner berikut. Setiap program harus mengambil satu atau dua angka 8-bit (A dan B) dari input dan menghitung operasi yang ditentukan:

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

Anda tidak harus menerapkan semua 5. Skor dihitung dengan:

#totalCharacters + {4000 * #problemsNotCompleted}

Jadi skor yang valid adalah dari nol (terbaik) hingga 20.000 (tidak ada yang selesai).

Saya tidak peduli di mana Anda menyimpan hasilnya, atau apakah Anda menyimpan input atau tidak. Asumsikan sel 8-bit, dan sel kosong sebanyak yang Anda butuhkan hanya di sebelah kanan.

Anda dapat mengasumsikan angkanya sudah di lokasi memori apa pun yang paling cocok untuk Anda, sehingga Anda tidak perlu khawatir tentang operasi IO.

captncraig
sumber
Bisakah kita juga menyelesaikan tugas dalam bahasa minimalis similary seperti iot?
FUZxxl
Saya tidak keberatan dengan bahasa lain, asalkan tidak ada operator bitwise bawaan.
captncraig

Jawaban:

7

Nilai: 275

Ini berfungsi lebih baik untuk memperluas ini dengan penghitung biner. Bagian-bagian yang kurang intuitif berurusan dengan kemungkinan bahwa A atau B adalah 0. Saya tidak menemukan cara yang menguntungkan untuk menggunakan kontrol aliran tidak rusak dalam manipulasi bit aktual dari tiga yang pertama. Kebetulan ini semua harus bekerja dengan baik dengan sel 16-bit dan perlahan-lahan dengan 32-bit.

XOR, 86

Asumsikan A dan B berada di sel 1 dan 2, menyimpan A XOR B di sel 2, penunjuk dimulai di sel 0 dan berakhir di sel 5.

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

DAN 78

Asumsikan A dan B berada di sel 1 dan 2, menyimpan A OR B di sel 4, penunjuk dimulai di sel 0 dan berakhir di sel 5.

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

ATAU, 86

Asumsikan A dan B berada di sel 1 dan 2, menyimpan A OR B di sel 2, penunjuk dimulai di sel 0 dan berakhir di sel 5.

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

ROL, 18

Asumsikan A ada di sel 0, simpan A ROL 1 di sel 1, penunjuk dimulai dan berakhir di sel 0.

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

TIDAK, 7

Asumsikan A ada di sel 0, simpan BUKAN di sel 1, penunjuk dimulai dan berakhir di sel 0.

+[>-<-]
Daniel Cristofani
sumber
Itu sangat singkat dan sangat keren. +1
salin
Peningkatan yang sangat mengesankan.
captncraig
8

Nilai: 686

Semua potongan mengasumsikan bahwa angka-angka sudah dimuat dalam sel 0 dan 1 dan bahwa pointer menunjuk ke sel 0. Saya dapat menambahkan potongan atoi nanti jika itu diperlukan untuk tantangan. Untuk saat ini, Anda dapat mencoba kode seperti ini:

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


XOR, 221

Hasilnya ditulis ke sel 10, penunjuk berakhir di sel 5

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

DAN, 209

Hasilnya ditulis ke sel 10, penunjuk berakhir di sel 5

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

ATAU, 211

Hasilnya ditulis ke sel 10, penunjuk berakhir di sel 5

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

Putar Kiri, 38

Hasil ditulis ke sel 1, penunjuk berakhir di sel 4

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

TIDAK, 7

Hasil ditulis ke sel 1, penunjuk berakhir di sel 0

+[+>+<]


Penjelasan:

XOR, AND dan OR semua bekerja dengan cara yang sama: Hitung n / 2 untuk setiap angka dan ingat n mod 2. Hitung XOR logis / DAN / ATAU untuk bit tunggal. Jika bit yang dihasilkan diatur, tambahkan 2 ^ n ke hasilnya. Ulangi itu 8 kali.

Ini adalah tata letak memori yang saya gunakan:

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

  8        9        10
temp  |  temp  |  result

Inilah sumber untuk XOR (angka menunjukkan di mana pointer berada pada waktu itu):

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

    <<<
]


Untuk rotate kiri, sekali lagi ada penanda di sel 2 untuk menentukan apakah 2n adalah nol, karena Anda hanya dapat menentukan apakah sel tersebut bukan nol secara langsung. Jika demikian, bit carry ditulis ke sel 4 dan kemudian ditambahkan ke 2n. Ini adalah susunan memori:

0      1        2       3       4   
n  |  2n  |  marker  |  0  |  carry 
salinan
sumber
Kerja bagus! Saya memang berniat untuk setiap program untuk mengambil input dari konsol, tetapi semakin saya memikirkannya, cara Anda berfungsi dengan baik. Tidak perlu membuat Anda menambahkan ,>,<. Saya akan mengedit pertanyaan.
captncraig
Saya akan tertarik mendengar sedikit penjelasan tentang bagaimana ini bekerja. Sepertinya tiga pertama Anda cukup mirip kecuali untuk bagian terdalam, tetapi saya tidak yakin apakah Anda melakukan semacam ekspansi biner (karenanya 8 sel diperlukan), atau sedikit demi sedikit membandingkan, atau kombinasi keduanya. Sulit dilihat dengan melangkah maju.
captncraig
@CMP Saya akan menambahkan penjelasan nanti
salin
3

Skor (saat ini): 12038 837 / -

Program mengasumsikan angka dimuat dalam sel apa pun yang ditentukan, oleh ,atau serupa. Ini juga mengasumsikan bahwa semua sel 8-bit tidak ditandai dengan pembungkus sesuai kebutuhan. Di awal setiap cuplikan, angka dimuat di sel 0 (dan 1 jika perlu).

Operasi bit - 799

Operasi bit mengikuti struktur umum yang sama.

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:

Putar Kiri A, 1 - 31 / -

Jumlahnya Adimuat dalam sel 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.

BUKAN A - 7

Jumlahnya Adimuat dalam sel 0.

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

+[->-<]
o_o
sumber