Programação Incondicional V

Alguns ifs simples, como o exemplo abaixo, podem ser substituídos por expressões.

if(a<b){
 x=c;
} else {
 x=d;
}

Esse bloco pode ser trocado por ((((a-b) >> 31) & (c^d)) ^ d), que pressupõe que estejam sendo usados inteiros de 32 bits e que o shift seja com sinal (vale em Java e na maior parte dos Cs).

O que ele faz é relativamente simples:

1. Subtrai b de a para produzir um número positivo se a for maior ou negativo se b for maior;
2. Executa um shift de 31 posições para produzir 0 se o número for positivo ou -1 (0xFFFFFFFF) se for negativo;
3. Executa um XOR de c com d e um AND do resultado com o valor do passo 2;
4. O AND do último passo vai produzir 0 ou c XOR d;
5. Se o valor do passo 4 for 0, o resultado final será d, porque 0 XOR d = d;
6. Se o valor do passo 4 for c XOR d, o resultado final será c, porque c XOR d XOR d = c.

Isso pode ser usado para tirar ifs de recursões. As recursões sempre têm um if para determinar quando parar, como no exemplo abaixo:

public int fact(int n) {
  if(n=1) {
    return 1;
  } else {
    return n * fact(n-1);
  }
}

O que se pode fazer nesse caso é escrever duas funções: uma sem recursão e uma com recursão. No exemplo abaixo, uso uma lista de funções e escolho qual usar conforme o valor de x.

public abstract class Factorial {

  protected abstract int fact(int x);

  private static class Factorial0 extends Factorial {
    @Override
    protected int fact(int x) {
      return 1;
    }
  }
  
  private static class FactorialN extends Factorial {
    @Override
    protected int fact(int x) {
      return x*getFunc(x-1).fact(x-1);
    }
  }
  
  
  private static Factorial[] funcs=new Factorial[] {
    new Factorial0(), new FactorialN()
  };
  
  protected static Factorial getFunc(int x) {
    return funcs[-1*(((1-x)>>31))];
  }
  
  public static int factorial(int x) {
    return getFunc(x).fact(x);
  }
  
  public static void main(String... args) {
    System.out.println(Factorial.factorial(Integer.parseInt(args[0])));
  }

}

A expressão -1*(((1-x)>>31)) é uma versão simplificada da expressão original, porque só é preciso retornar 1 quando x>1 ou 0 se x<=1. A expressão (1-x)>>31 sempre retorna 0 ou -1, então a multiplicação por -1 transforma isso em 0 ou 1, que podemos usar para indexar a lista de funções.

É mais complicado, mas não tem ifs!