找出单元格中的数字是偶数还是奇数

Question

鉴于磁带的第0个单元格中的数字已被填充,其余部分仅用作刮擦单元格(即它们都从0开始并且是临时的 - 我不在乎它们发生了什么),我想要更换第0个单元格为0或1. 0表示偶数,1表示奇数.

基本上,我想做的是(在C-esque伪代码中):

cell[0] = (cell[0] % 2)

我知道有一个divmod算法定义如下:

如果不需要保留n,请使用以下变体:

# >n d
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d

但是,因为X % 2 == X & 1,即X mod 2是X的最右边,我认为divmod在计算的复杂性方面可能过度.

是否有更好的算法/技术来确定细胞是否均匀？

Answer 1

你需要一个只保持奇偶校验的算法,你可以这样做:

result=0
while(n > 0) {
  result++;
  n--;
  if(n > 0) {
    result--;
    n--;
  }
}

要测试n而不丢失它的值,你需要复制它:从A复制到B和C然后将C移动到A.你可以测试B并将n保持为A.这是brainfuck代码:

[->+<] # move @0 to @1
> # goto @1
[-<+ # if @1 then decrements @1 and increments @0
 > # goto @1
 [->+>+<<] # if @1 then move @1 to @2 and @3
 >> # goto @3
 [-<<+>>] # if @3 then move @3 to @1
 < # goto @2
 [<-<->>[-]] # if @2 then decrements @0, decrements @1 and sets 0 into @2
 < # go to @1
] # continue loop if @1 is not null
< # goto @0

光形式:

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