Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Can we also solve the task in a similary minimalistic language such as iot? –  FUZxxl Dec 11 '12 at 11:37
    
I have no objections to any other languages, as long as there are no built in bitwise operators. –  CMP Dec 11 '12 at 16:53

3 Answers 3

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 
share|improve this answer
    
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. –  CMP Dec 11 '12 at 18:37
    
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. –  CMP Dec 11 '12 at 19:27
    
@CMP I'll add an explanation later –  copy Dec 11 '12 at 19:43

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 OR 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.

+[>-<-]
share|improve this answer
    
That's really short and pretty cool. +1 –  copy Nov 16 '13 at 18:46
    
Seriously impressive improvements. –  CMP Nov 19 '13 at 5:48

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

+[->-<]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.