sexta-feira, 10 de fevereiro de 2012

Encontrar o menor entre dois inteiros sem utilizar o operador de comparação

Para descobrir o menor entre dois inteiros sem utilizar a operador de comparação, precisamos saber um pouco
sobre a representação dos números inteirosem notação complemento de dois.

Primeiramente, sabemos que INT_MIN<=x-y<=INT_MAX.
O bit mais significativo (most significant bit) corresponde ao sinal de um número em notação complemento de dois."1"  significa negativo e "0" significa positivo.

A seguinte operação pega o bit mais significativo
#define CHAR_BIT 8 (x-y)>> (sizeof(int)*CHAR_BIT - 1)

A operação sizeof(int) retorna a quantidade de bytes de um inteiro, ou seja, 4 bytes e 8 é a quantidade de bits em cada byte. O operador >> faz o deslocamento para direita. Logo, a operação completa  >> (sizeof(int)*CHAR_BIT - 1) desloca 31 bits para a direita sobrando apenas o bit mais significativo. Se x-y>=0 então x-y>>31 será igual 0. Logo, y será o menor. Se x-y<0 então x-y>>31 será 1. Logo, x será o menor.

#include <stdio.h>
#include <stdlib.h>
#define CHAR_BIT 8

int min(int x,int y){
  if( (x-y)>> (sizeof(int)*CHAR_BIT - 1) ){
    return x;
  }else{
    return y;
  }
}

int main(){
  printf("%d\n",min(28,22));
}

Nenhum comentário: