Como faço para programaticamente devolver o máximo de dois inteiros sem usar operadores de comparação e sem utilizar if, else, etc?
-
03-07-2019 - |
Pergunta
Como posso devolver programaticamente o máximo de dois inteiros sem usar operadores de comparação e sem utilizar if
, else
, etc?
Solução
max: // Will colocou MAX (a, b) em um
a -= b;
a &= (~a) >> 31;
a += b;
E:
int a, b;
min: // Will colocou MIN (a, b) em um
a -= b;
a &= a >> 31;
a += b;
aqui .
Outras dicas
http://www.graphics.stanford.edu/~seander /bithacks.html#IntegerMinOrMax
r = x - ((x - y) & -(x < y)); // max(x, y)
Você pode se divertir com aritmeticamente deslocando (x - y)
para saturar o bit de sinal, mas isso geralmente é suficiente. Ou você pode testar o bit alto, sempre divertido.
Eu acho que eu tenho.
int data[2] = {a,b};
int c = a - b;
return data[(int)((c & 0x80000000) >> 31)];
Será que isso não funciona? Basicamente, você pega a diferença dos dois, e em seguida, retornar um ou outro baseado no bit de sinal. (Esta é a forma como o processador faz maior ou menor do que de qualquer maneira.) Então, se o bit de sinal é 0, retornar um, já que um é maior ou igual a b. Se o bit de sinal é 1, o retorno b, porque subtrair b de um causou o resultado para ir negativo, indicando que b foi maior do que um. Apenas certifique-se de que seus ints são 32bits assinados.
No mundo da matemática:
max(a+b) = ( (a+b) + |(a-b)| ) / 2
min(a-b) = ( (a+b) - |(a-b)| ) / 2
Além de ser matematicamente correto não é fazer suposições sobre o tamanho pouco como deslocando operações precisa fazer.
|x|
representa o valor absoluto de x.
Comentário:
Você está certo, o valor absoluto foi esquecido. Este deve ser válida para todos a, b positivo ou negativo
retorno (a> b a:? B);
ou
int max(int a, int b)
{
int x = (a - b) >> 31;
int y = ~x;
return (y & a) | (x & b);
}
não tão snazzy como o acima ... mas ...
int getMax(int a, int b)
{
for(int i=0; (i<a) || (i<b); i++) { }
return i;
}
Uma vez que este é um quebra-cabeça, solução será um pouco complicado:
let greater x y = signum (1+signum (x-y))
let max a b = (greater a b)*a + (greater b a)*b
Esta é Haskell, mas será o mesmo em qualquer outra língua. C / C # pessoas devem usar "SGN" (ou "sinal"?) Em vez de signum.
Note que este irá funcionar em ints de tamanho arbitrário e em reais também.
De (famoso escritor virii) O artigo de z0mbie "polimórficos Games", talvez você vai achar que é útil:
#define H0(x) (((signed)(x)) >> (sizeof((signed)(x))*8-1))
#define H1(a,b) H0((a)-(b))
#define MIN1(a,b) ((a)+(H1(b,a) & ((b)-(a))))
#define MIN2(a,b) ((a)-(H1(b,a) & ((a)-(b))))
#define MIN3(a,b) ((b)-(H1(a,b) & ((b)-(a))))
#define MIN4(a,b) ((b)+(H1(a,b) & ((a)-(b))))
//#define MIN5(a,b) ((a)<(b)?(a):(b))
//#define MIN6(a,b) ((a)>(b)?(b):(a))
//#define MIN7(a,b) ((b)>(a)?(a):(b))
//#define MIN8(a,b) ((b)<(a)?(b):(a))
#define MAX1(a,b) ((a)+(H1(a,b) & ((b)-(a))))
#define MAX2(a,b) ((a)-(H1(a,b) & ((a)-(b))))
#define MAX3(a,b) ((b)-(H1(b,a) & ((b)-(a))))
#define MAX4(a,b) ((b)+(H1(b,a) & ((a)-(b))))
//#define MAX5(a,b) ((a)<(b)?(b):(a))
//#define MAX6(a,b) ((a)>(b)?(a):(b))
//#define MAX7(a,b) ((b)>(a)?(b):(a))
//#define MAX8(a,b) ((b)<(a)?(a):(b))
#define ABS1(a) (((a)^H0(a))-H0(a))
//#define ABS2(a) ((a)>0?(a):-(a))
//#define ABS3(a) ((a)>=0?(a):-(a))
//#define ABS4(a) ((a)<0?-(a):(a))
//#define ABS5(a) ((a)<=0?-(a):(a))
aplausos
Esta é uma espécie de batota, usando linguagem assembly, mas é interessante mesmo assim:
// GCC inline assembly
int max(int a, int b)
{
__asm__("movl %0, %%eax\n\t" // %eax = a
"cmpl %%eax, %1\n\t" // compare a to b
"cmovg %1, %%eax" // %eax = b if b>a
:: "r"(a), "r"(b));
}
Se você quiser ser rigoroso sobre as regras e dizer que a instrução cmpl
é ilegal para isso, então o seguinte sequência (menos eficiente) funcionará:
int max(int a, int b)
{
__asm__("movl %0, %%eax\n\t"
"subl %1, %%eax\n\t"
"cmovge %0, %%eax\n\t"
"cmovl %1, %%eax"
:: "r"(a), "r"(b)
:"%eax");
}
int max(int a, int b)
{
return ((a - b) >> 31) ? b : a;
}