Da série "Fiz errado a vida toda e ninguém percebeu"
Ana Luiza Basalo
em 25 de Fevereiro de 2014

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 (231 - 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 -231 (em decimal: -2147483648, em binário no Java: 10000000 00000000 00000000 00000000) a 231-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 231 (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é!

São Paulo / SP
Graduação: Ciência da Computação (Instituto de Matemática e Estatística da USP)
Formou-se com honra ao mérito em Ciência da Computação no IME-USP em 2011. Já atuou como administradora de redes e como analista de sistemas e programadora (sistemas Web e apps para Android). Também foi professora voluntária de Matemática (Ensino Básico) e monitora em algumas disciplinas de graduação em Computação na USP. Além disso, por hobby, atua como professora particular nas horas vagas. As aulas particulares são preparadas conforme a necessidade dos alunos: pode ser dada maior atençã ...
Computação - Autômatos, Computação - Programação, Computação e Informática a domicílio, Programação em Java, Programação em C
Oferece aulas presenciais
R$ 80 / aula
Conversar
1ª aula gratuita
Cadastre-se ou faça o login para comentar nessa publicação.

Listas de exercícios, Documentos, Revisões de textos, Trabalhos?

Se seu problema for dificuldade em uma lista de exercícios, revisão de teses e dissertações, correção de textos ou outros trabalhos, peça uma ajuda pelo Tarefas Profes.

Enviar Tarefa

Confira artigos similares

Confira mais artigos sobre educação

Ver todos os artigos

Encontre um professor particular

Busque, encontre e converse gratuitamente com professores particulares de todo o Brasil