15
\$\begingroup\$

Your task is to create one brainfuck program for each of the following binary operators. Each program should take one or two 8-bit numbers (A and B) from input and calculate the specified operation:

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

You do not have to implement all 5. Score is calculated by:

#totalCharacters + {4000 * #problemsNotCompleted}

So valid scores are from zero (best) to 20,000(nothing completed).

I don't care where you store the result, or whether or not you preserve the input. Assume 8-bit cells, and as many empty cells as you need to the right only.

You may assume the numbers are already in whatever memory location works best for you, so you don't need to worry about IO operations.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Can we also solve the task in a similary minimalistic language such as iot? \$\endgroup\$ Commented Dec 11, 2012 at 11:37
  • \$\begingroup\$ I have no objections to any other languages, as long as there are no built in bitwise operators. \$\endgroup\$ Commented Dec 11, 2012 at 16:53

3 Answers 3

Reset to default
12
\$\begingroup\$

Score: 275

It works better to expand these with a binary counter. The less intuitive parts deal with the possibility that A or B is 0. I didn't find a profitable way to use nondestructive flow control in the actual bit manipulation of the first three. Incidentally these should all work fine with 16-bit cells and slowly with 32-bit.

XOR, 86

Assumes A and B are in cells 1 and 2, stores A XOR B in cell 2, pointer starts in cell 0 and ends in cell 5.

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

AND, 78

Assumes A and B are in cells 1 and 2, stores A AND B in cell 4, pointer starts in cell 0 and ends in cell 5.

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

OR, 86

Assumes A and B are in cells 1 and 2, stores A OR B in cell 2, pointer starts in cell 0 and ends in cell 5.

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

ROL, 18

Assumes A is in cell 0, stores A ROL 1 in cell 1, pointer starts and ends in cell 0.

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

NOT, 7

Assumes A is in cell 0, stores NOT A in cell 1, pointer starts and ends in cell 0.

+[>-<-]
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ That's really short and pretty cool. +1 \$\endgroup\$ Commented Nov 16, 2013 at 18:46
  • \$\begingroup\$ Seriously impressive improvements. \$\endgroup\$ Commented Nov 19, 2013 at 5:48
8
\$\begingroup\$

Score: 686

All snippets assume that the numbers are already loaded in cell 0 and 1 and that the pointer points to cell 0. I can add an atoi snippet later if that's required for the challenge. For now, you can try the code like this:

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


XOR, 221

Result is written to cell 10, pointer ends at cell 5

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

AND, 209

Result is written to cell 10, pointer ends at cell 5

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

OR, 211

Result is written to cell 10, pointer ends at cell 5

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

Rotate Left, 38

Result is written to cell 1, pointer ends at cell 4

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

NOT, 7

Result is written to cell 1, pointer ends at cell 0

+[+>+<]


Explanation:

XOR, AND and OR all work in a similiar fashion: Calculate n/2 for each number and remember n mod 2. Calculate the logical XOR/AND/OR for the single bits. If the resulting bit is set, add 2^n to the result. Repeat that 8 times.

This is the memory layout I used: 

 0 1 2 3 4 5 6 7 n1 | n2 | marker | n/2 | 0 | counter | bit1 | bit2 | 8 9 10 temp | temp | result

Here's the source for XOR (numbers indicate where the pointer is at that time):

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


For left rotate, once again there is a marker in cell 2 to determine if 2n is zero, since you can only determine if a cell is non-zero directly. If so, a carry bit is written to cell 4 and later added to 2n. This is the memory layout:

0 1 2 3 4 n | 2n | marker | 0 | carry
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Great work! I did intend for each program to take input from the console, but the more I think about it, your way works fine. No need to make you add ,>,<. I'll edit question. \$\endgroup\$ Commented Dec 11, 2012 at 18:37
  • \$\begingroup\$ I would be interested to hear a bit of an explanation for how these are working. It looks like your first three are pretty similar except for the innermost part, but I am not sure if you are doing some kind of binary expansion (hence 8 cells needed), or a bit by bit compare, or some combination of the two. Hard to see by stepping through. \$\endgroup\$ Commented Dec 11, 2012 at 19:27
  • \$\begingroup\$ @CMP I'll add an explanation later \$\endgroup\$ Commented Dec 11, 2012 at 19:43
3
\$\begingroup\$

Score (current): 12038 837/-

The programs assume numbers are loaded in whatever cell is specified, by , or similar. It also assumes that all cells are 8-bit unsigned with wrapping as needed. At the start of each snippet, numbers are loaded at cell 0 (and 1 if needed).

Bit operations - 799

The bit operations follow the same general structure.

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:

Rotate Left A, 1 - 31/-

The number A is loaded in cell 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.

NOT A - 7

The number A is loaded in cell 0.

Pseudocode $0 := A $0 += 1 $1 := 256-$0 #since ~A=255-A res := $1 +[->-<]
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.