quinta-feira, 21 de janeiro de 2010

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!

Nenhum comentário: