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

Question

鉴于磁带的第 0 个单元格中的数字已被填充，其余的都只是用作临时单元格(即它们都从 0 开始并且是临时的——我不在乎它们会发生什么)，我会喜欢用 0 或 1 替换第 0 个单元格。偶数为 0，奇数为 1。

基本上，我想做的是(用 C 风格的伪代码):

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

我知道存在一个 divmod algorithm定义如下:

If one does not need to preserve n, use this variant:

# >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 移动到 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

轻型:

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