Bitwise Operators in Brainfuck

Question

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.

Answer 1

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.

+[>-<-]

Answer 2

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 

Answer 3

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

+[->-<]