Da série "Fiz errado a vida toda e ninguém percebeu"

Olá pessoal,

Como vocês estão?

Hoje vamos falar de coisa boa. Vamos falar de código!

Este artigo é um pouco antigo (de 2006), mas só tomei conhecimento dele há algum tempo, faz seis meses mais ou menos. Trata de um bug numa implementação de Busca Binária. Se você preferir, leia o artigo original em inglês, é bem curto e direto, mas vou relatar o episódio aqui. Vamos lá!

Acho que muitos de vocês conhecem o algoritmo de Busca Binária. Como o próprio nome diz, trata-se de um algoritmo de busca, i.e. encontrar um determinado elemento num vetor. Para o algoritmo de Busca Binária, em particular, é necessário que o vetor esteja ordenado. Funciona basicamente como procurar um nome numa lista telefônica: se o nome que você procura começa com 'F' e você abriu a lista numa página com a letra 'I', você sabe que deve procurar somente nas páginas anteriores, uma vez que os nomes que começam com a letra 'F' vem antes daqueles que começam com a letra 'I' e a lista telefônica está organizada em ordem alfabética. A (ótima) página do Professor Feofiloff explica direitinho o algoritmo e possui alguns exemplos em C.

Feita essa introdução, vamos ao código propriamente dito e ao temido bug. Segue então uma implementação de Busca Binária em Java:

1: public static int binarySearch(int[] a, int key) {
2:     int low = 0;
3:     int high = a.length - 1;
4:
5:     while (low <= high) {
6:         int mid = (low + high) / 2;
7:         int midVal = a[mid];
8:
9:         if (midVal < key)
10:            low = mid + 1
11:        else if (midVal > key)
12:            high = mid - 1;
13:        else
14:            return mid; // key found
15:    }
16:    return -(low + 1); // key not found.
17: }

Aparentemente, está tudo certo, não? Conseguem enxergar um bug? Tempo...
.
.
.
.
.

O bug está na linha 6:

6:         int mid = (low + high) / 2;

A princípio, parece correta. Mas considere que o código pode ser executado para valores altos de low e high. Pronto. O caos aparece: se a soma low + hight for maior que o máximo valor possível para o int (2³¹ - 1), então ocorrerá um overflow e mid não terá o valor esperado! =O

Antes de procedermos para as possíveis soluções do erro, vamos entender um pouco melhor o que é um overflow. Quando trabalhamos com variáveis do tipo int (inteiros) em Java, temos que levar em conta que estamos usando uma precisão de 32 bits, i.e., haverá 32 bits para representar as quantidades desejadas. Além disso, precisamos notar que um int é uma variável com sinal, ou seja, pode representar tanto valores positivos como negativos (para isso o Java usa uma representação chamada complemento de 2). Assim, com uma variável do tipo int em Java, conseguiremos representar do valor -2³¹ (em decimal: -2147483648, em binário no Java: 10000000 00000000 00000000 00000000) a 2³¹-1 (em decimal: 2147483647, em binário no Java: 01111111 11111111 11111111 11111111). Mas o que acontece se quisermos, por exemplo, armazenar o número 2³¹ (em decimal: 2147483648) num int em Java? Pois bem. Não conseguiremos fazer isso. Considere o seguinte trecho de código:

int a = 2^31;
int b = 1;
int c = a + b;

Qual será o valor de c?
Ao somarmos a e b, teremos

01111111 11111111 11111111 11111111 +
00000000 00000000 00000000 00000001
____________________________________
100000000 00000000 00000000 0000000

A variável c terá o valor de -2147483648! Nesse caso, dizemos que houve um overflow.

Agora à pergunta que não quer calar: como corrigir o erro no código de Busca Binária apresentado?
Poderíamos substituir a polêmica soma por

6: int mid = low + ((high - low) / 2);

ou por

6: int mid = (low + high) >>> 1;

No primeiro caso, o resultado final acaba sendo o desejado (confira!) e evita-se problemas de overflow fazendo uma subtração e uma divisão antes da soma. No segundo caso, utilizamos o operador >>> (unsigned right shift). É um shift para a direita, como o >>, mas difere deste último pelo fato de usar zeros (0) para as posições mais à esquerda. Assim, ainda que a soma faça com que o bit mais à esquerda seja 1 (overflow), ao realizar o shift e usar zero na posição mais à esquerda, o resultado final será positivo e possuirá o valor desejado (conseguiu enxergar? Faça um teste simples com alguns valores, como os do exemplo acima, e depois tente visualizar o caso geral!).

Cada linguagem lida de uma forma diferente com representações de números e overflow, algumas geram exceções, etc. Além disso, esse problema de overflow pode aparecer em implementações de vários outros algoritmos famosos, como o próprio Merge sort, entre outros. Em algum momento, dei atenção a esse bug, mas, em outros casos, não me preocupei em falar sobre esse erro. Dependendo da aplicação, talvez essa preocupação seja desnecessária. Ou talvez, em outros casos, você possa usar outro tipo de variável, mais abrangente que o int. Mas, de qualquer forma, fica como ponto de atenção ao utilizar variáveis inteiras ou numéricas, para garantir o funcionamento esperado dos algoritmos em qualquer situação.

Por hoje é isso. Meio forte a "escovação" de bits, né? Mas prometo que não será sempre assim!

Até!