説明的な

メモリの使い方（追記の方）

• 0 番地と 34 番地に番兵として -1 を置く。
• 1, 3, ..., 33 番地に 17 bit のデータ。
• 2, 4, ..., 32 番地は xor の作業用領域兼 0 番地や 34 番地に移動するための足場。
• 35 番地はループカウンタ。
• 36 番地に入力文字読み込み。
• 37 番地以降は入力文字の 2 進数化の作業領域。

2進数化のために

こんな感じで p[3]=p[0]%2、p[4]=p[0]/2 を計算してます。

// p[3]==p[4]==0 とする
while(p[0]!=0){
    if(p[0]!=0){
        p[0]--;
        p[3]++;
    }
    if(p[0]!=0){
        p[0]--;
        p[3]--;
        p[4]++;
    }
}

もう少し Brainfuck っぽくすると、

// p[1]==p[2]==p[3]==p[4]==0 とする
while(p[0]!=0){
    // p[1]=p[2]=p[0];
    while(p[0]!=0){
        p[0]--;
        p[1]++;
        p[2]++;
    }
    // if(p[2]!=0) p[1]--, p[3]++;
    while(p[2]!=0){
        while(p[2]!=0) p[2]--;
        p[1]--;
        p[3]++;
    }
    // p[0]=p[2]=p[1];
    while(p[1]!=0){
        p[1]--;
        p[0]++;
        p[2]++;
    }
    // if(p[2]!=0) p[0]--, p[3]--, p[4]++;
    while(p[2]!=0){
        while(p[2]!=0) p[2]--;
        p[0]--;
        p[3]--;
        p[4]++;
    }
}

xor

0 か 1 のどちらかが入っている p[0] と p[2] に対して

if(p[2]) p[0]=1-p[0];

みたいな感じで p[0]^=p[2] を計算してます。実際にはこんな感じです。

// p[1]==0 とする。
while(p[2]!=0){
    p[2]--;
    while(p[0]!=0){
        p[0]--;
        p[1]++;
    }
    while(p[1]!=0){
        p[1]--;
        p[0]--;
    }
    p[0]++;
}