ti-enxame.com

Explique este snippet que encontra o máximo de dois inteiros sem usar o if-else ou qualquer outro operador de comparação?

Encontre o máximo de dois números. Você não deve usar if-else ou qualquer outro operador de comparação. Eu encontrei esta pergunta no boletim on-line, então eu pensei que deveria perguntar no StackOverflow

EXEMPLO Entrada: 5, 10 Saída: 10

Eu encontrei esta solução, alguém pode me ajudar a entender essas linhas de código

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}
74
SuperMan
int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

Vamos dissecar isso. Esta primeira linha parece ser direta - armazena a diferença de a e b. Este valor é negativo se a < b e não é negativo de outra forma. Há realmente um erro aqui - se a diferença dos números a e b é tão grande que não cabe em um inteiro, isso levará a um comportamento indefinido - oops! Então vamos supor que isso não aconteça aqui.

Na próxima linha, que é

int k = (c >> 31) & 0x1;

a ideia é verificar se o valor de c é negativo. Em praticamente todos os computadores modernos, os números são armazenados em um formato chamado complemento de dois em que o maior bit do número é 0 se o número for positivo e 1 se o número for negativo. Além disso, a maioria dos ints é de 32 bits. (c >> 31) desloca o número para baixo em 31 bits, deixando o bit mais alto do número no local para o bit mais baixo. O próximo passo de pegar esse número e ANDing it com 1 (cuja representação binária é 0 em todos os lugares, exceto o último bit) apaga todos os bits mais altos e apenas fornece o bit mais baixo. Como o bit mais baixo de c >> 31 é o bit mais alto de c, ele lê o bit mais alto de c como 0 ou 1. Como o bit mais alto é 1 iff c é 1, essa é uma forma de verificar se c é negativo (1) ou positivo (0). Combinando este raciocínio com o acima, k é 1 se a < b e é 0 caso contrário.

O passo final é fazer isso:

int max = a - k * c;

Se a < b, k == 1 e k * c = c = a - b, e assim

a - k * c = a - (a - b) = a - a + b = b

Qual é o máximo correto, desde a < b. Caso contrário, se a >= b, k == 0 e

a - k * c = a - 0 = a

Qual é também o máximo correto.

116
templatetypedef

Aqui vamos nós: (a + b) / 2 + |a - b| / 2

28
mike.dld

Use hackers bit a bit

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

Se você souber INT_MIN <= x - y <= INT_MAX,, poderá usar o seguinte, que é mais rápido porque (x - y) precisa ser avaliado apenas uma vez.

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

Fonte: Bit Twiddling Hacks de Sean Eron Anderson

19
Prasoon Saurav
(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

Isto é baseado na mesma técnica que a solução mike.dld , mas é menos "óbvio" aqui o que estou fazendo. Uma operação "abs" parece que você está comparando o sinal de alguma coisa, mas eu estou tirando proveito do fato de que sqrt () sempre retornará a raiz quadrada positiva, então estou alinhando (ab) escrevendo completamente enraizando-o novamente, adicionando a + be dividindo por 2.

Você verá que sempre funciona: por exemplo, o exemplo do usuário de 10 e 5 você obtém o sqrt (100 + 25 - 100) = 5, em seguida, adiciona 10 e 5 dá 20 e divide por 2 dá 10.

Se usarmos 9 e 11 como nossos números obteríamos (sqrt (121 + 81 - 198) + 11 + 9)/2 = (sqrt (4) + 20)/2 = 22/2 = 11

11
CashCow

A resposta mais simples está abaixo. 

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}
8
novice
int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

Esta solução evita a multiplicação. M será 0x00000000 ou 0xffffffff

4
vikky.rk

Usando a ideia de mudança para extrair o sinal como postado por outros, aqui está outra maneira:

max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]

Isso coloca os dois números em uma matriz com o número máximo dado pelo elemento array cujo índice é um bit de sinal da diferença entre os dois números.

Observe que:

  1. A diferença (a - b) pode estourar.
  2. Se os números não estiverem assinados e o operador >> se referir a um deslocamento de logical right, o & 1 será desnecessário.
3
Ani

Aqui está como eu acho que faria o trabalho. Não é tão legível quanto você gostaria, mas quando você começa com "como eu faço X sem usar a maneira óbvia de fazer X, você tem que esperar isso. Em teoria, isso desiste de alguma portabilidade também, mas você teria que encontrar um sistema bastante incomum para ver um problema.

#define BITS (CHAR_BIT * sizeof(int) - 1)

int findmax(int a, int b) { 
    int rets[] = {a, b};
    return rets[unsigned(a-b)>>BITS];
}

Isso tem algumas vantagens sobre o mostrado na questão. Primeiro de tudo, ele calcula o tamanho correto do turno, em vez de ser codificado para ints de 32 bits. Segundo, com a maioria dos compiladores, podemos esperar que toda a multiplicação aconteça em tempo de compilação, de modo que tudo o que resta no tempo de execução é a manipulação (subtração e deslocamento) de bits triviais, seguida por uma carga e retorno. Em suma, é quase certo que isso será bastante rápido, mesmo no menor microcontrolador, em que o original usou a multiplicação que tinha que acontecer em tempo de execução, então, embora seja provavelmente muito rápido em uma máquina de desktop, muitas vezes será bastante pouco mais devagar em um pequeno microcontrolador.

3
Jerry Coffin

Veja o que essas linhas estão fazendo:

c é a-b. se c for negativo, a <b.

k é 32º bit de c que é o bit de sinal de c (assumindo 32 bits inteiros. Se feito em uma plataforma com inteiros de 64 bits, este código não funcionará). Ele é deslocado 31 bits para a direita para remover os 31 bits mais à direita, deixando o bit de sinal no lugar mais à direita e, em seguida, usando 1 para remover todos os bits à esquerda (que será preenchido com 1s se c for negativo). Então k será 1 se c for negativo e 0 se c for positivo.

Então max = a - k * c. Se c for 0, isso significa a> = b, então max é a - 0 * c = a. Se c for 1, isso significa que a <b e depois a - 1 * c = a - (a - b) = a - a + b = b.

No geral, é apenas usar o bit de sinal da diferença para evitar usar operações maiores ou menores que. É honestamente um pouco bobo dizer que esse código não usa uma comparação. c é o resultado da comparação entre a e b. O código simplesmente não usa um operador de comparação. Você pode fazer uma coisa semelhante em muitos códigos de montagem apenas subtraindo os números e, em seguida, saltando com base nos valores definidos no registro de status.

Devo também acrescentar que todas essas soluções estão assumindo que os dois números são inteiros. Se eles são floats, doubles, ou algo mais complicado (BigInts, números Rational, etc), então você realmente tem que usar um operador de comparação. Os truques de bits geralmente não são para eles.

2
Keith Irwin

função getMax () sem qualquer operação lógica

int getMax(int a, int b){
    return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2;
}

Explicação:

Vamos quebrar o 'max' em pedaços,

max
= ( max + max ) / 2
= ( max + (min+differenceOfMaxMin) ) / 2
= ( max + min + differenceOfMaxMin ) / 2
= ( max + min + | max - min | ) ) / 2

Então, a função deve se parecer com isso

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2

Agora,

absolute(x)
= x [if 'x' is positive] or -x [if 'x' is negative]
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )

Em número positivo inteiro, o primeiro bit (bit de sinal) é - 0; em negativo é- 1. Deslocando bits para a direita (>>) o primeiro bit pode ser capturado.

Durante o turno da direita, o espaço vazio é preenchido pelo bit de sinal. Então 01110001 >> 2 = 00011100, enquanto 10110001 >> 2 = 11101100.

Como resultado, para troca de números de 8 bits, 7 bits produzirão 1 1 1 1 1 1 [0 ou 1] para negativo, ou 0 0 0 0 0 0 0 [0 ou 1] para positivo.

Agora, se a operação OU for executada com 00000001 (= 1), o número negativo gera _ 11111111 (= -1) e positivo _ 00000001 (= 1).

Assim,

absolute(x)
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
= x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 )
= x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 )
= x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )

Finalmente,

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2
1
Minhas Kamal
#include<stdio.h>
main()
{
        int num1,num2,diff;
        printf("Enter number 1 : ");
        scanf("%d",&num1);
        printf("Enter number 2 : ");
        scanf("%d",&num2);
        diff=num1-num2;
        num1=abs(diff);
        num2=num1+diff;
        if(num1==num2)
                printf("Both number are equal\n");
        else if(num2==0)
                printf("Num2 > Num1\n");
        else
                printf("Num1 > Num2\n");
}
0
Chirag

O código que estou fornecendo é para encontrar o máximo entre dois números, os números podem ser de qualquer tipo de dados (inteiro, flutuante). Se os números de entrada forem iguais, a função retornará o número.

double findmax(double a, double b)
{
    //find the difference of the two numbers
    double diff=a-b;
    double temp_diff=diff;
    int int_diff=temp_diff;
    /*
      For the floating point numbers the difference contains decimal
      values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need
      to get a non-zero number on the left side of '.'
    */
    while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) )
    {
       temp_diff = temp_diff * 10;
       int_diff = temp_diff;
    }
    /*
      shift the sign bit of variable 'int_diff' to the LSB position and find if it is 
      1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of
      the two numbers (variable 'diff') then subtract it with the variable a.
    */
    return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 ));
}

Descrição

  • A primeira coisa que a função considera os argumentos como double e retorna type como double. A razão para isso é que para criar uma única função que pode encontrar o máximo para todos os tipos. Quando números de tipo inteiro são fornecidos ou um é um número inteiro e outro é o ponto flutuante, então também devido à conversão implícita, a função pode ser usada para encontrar o máximo para números inteiros também.
  • A lógica básica é simples, digamos que temos dois números a & b se ab> 0 (ou seja, a diferença é positiva) então a é o máximo mais se ab == 0 então ambos são iguais e se ab <0 (ie diff é - ve) b é o máximo.
  • O bit de sinal é salvo como o Bit Mais Significativo (MSI) na memória. Se MSB é 1 e vice-versa. Para verificar se o MSB é 1 ou 0, mudamos o MSB para a posição LSB e Bitwise & com 1, se o resultado for 1, então o número é -ve else no. é + ve. Este resultado é obtido pela declaração:

    int_diff >> (sizeof (int) * 8 - 1) & 1

Aqui para obter o bit de sinal do MSB para o LSB nós o deslocamos para direita para k-1 bits (onde k é o número de bits necessários para salvar um número inteiro na memória que depende do tipo de sistema). Aqui k = sizeof (int) * 8 como sizeof () fornece o número de bytes necessários para salvar um inteiro para obter no. de bits, nós multiplicamos com 8. Após o turno certo, aplicamos o bit a bit e com 1 para obter o resultado.

  • Agora, depois de obter o resultado (vamos assumir como r) como 1 (para -ve diff) e 0 (para + ve diff) multiplicamos o resultado com a diferença dos dois números, a lógica é dada da seguinte forma:

    1. se a> b, então a-b> 0, ou seja, é + ve, então o resultado é 0 (isto é, r = 0). Então a- (a-b) * r => a- (a-b) * 0, que dá 'a' como o máximo.
    2. se a <b então a-b <0, isto é, -ve então o resultado é 1 (isto é, r = 1). Então a- (a-b) * r => a- (a-b) * 1 => a-a + b => b, que dá 'b' como o máximo.
  • Agora existem dois pontos restantes: 1. o uso de loop while e 2. por que eu usei a variável 'int_diff' como um inteiro. Para respondê-las corretamente, precisamos entender alguns pontos:

    1. Valores de tipo flutuante não podem ser usados ​​como um operando para os operadores bit a bit.
    2. Devido ao motivo acima, precisamos obter o valor em um valor inteiro para obter o sinal de diferença usando operadores bit a bit. Esses dois pontos descrevem a necessidade da variável 'int_diff' como tipo inteiro.
    3. Agora digamos que encontramos a diferença na variável 'diff' agora há 3 possibilidades para os valores de 'diff' independentemente do sinal desses valores. (uma). | diff |> = 1, (b). 0 <| diff | <1, (c). | diff | == 0.
    4. Quando atribuímos um valor duplo à variável inteira, a parte decimal é perdida.
    5. Para o caso (a), o valor de 'int_diff'> 0 (ou seja, 1,2, ...). Para outros dois casos int_diff = 0.
    6. A condição (temp_diff-int_diff) || 0.0 verifica se diff == 0, então ambos os números são iguais.
    7. Se diff! = 0 então verificamos se int_diff | 0 é verdadeiro, ou seja, caso (b) é verdadeiro
    8. No loop while, tentamos obter o valor de int_diff como diferente de zero, para que o valor de int_diff também receba o sinal de diff.
0
ashesh

// Em C # você pode usar a biblioteca de matemática para executar a função min ou max

usando o sistema;

classe NumberComparator {

static void Main()
{

    Console.Write(" write the first number to compare: ");
    double first_Number = double.Parse(Console.ReadLine());

    Console.Write(" write the second number to compare: ");
    double second_Number = double.Parse(Console.ReadLine());

    double compare_Numbers = Math.Max(first_Number, second_Number);
    Console.Write("{0} is greater",compare_Numbers);

}

}

0

estático int mymax (int a, int b)

    {
        int[] arr;
        arr = new int[3];
        arr[0] = b;
        arr[1] = a;
        arr[2] = a;
        return arr[Math.Sign(a - b) + 1];

    }

Se b> a então (ab) será negativo, o sinal retornará -1, adicionando 1, obtemos o índice 0, que é b, se b = a, então ab será 0, +1 dará 1 índice, então não importa. se estivermos retornando a ou b, quando a> b, então, ab será positivo e o sinal retornará 1, adicionando 1, obtemos o índice 2, onde a é armazenado. 

0
Raj Saraf

Aqui estão alguns métodos bit-twiddling para obter o máximo de dois valores integrais:

Método 1

int max1(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return (a & ~mask) | (b & mask);
}

Explicação:

  • (a - b) >> SIGN_BIT_SHIFT - Se a > b, a - b é positivo, o bit de sinal é 0 e a máscara é 0x00.00. Caso contrário, a < b so a - b é negativo, o bit de sinal é 1 e após a mudança, obtemos uma máscara de 0xFF..FF
  • (a & ~ mask) - Se a máscara é 0xFF..FF, então ~mask é 0x00..00 e então este valor é 0. Caso contrário, ~mask é 0xFF..FF e o valor é a
  • (b & mask) - Se a máscara for 0xFF..FF, esse valor será b. Caso contrário, mask é 0x00..00 e o valor é 0.

Finalmente:

  • Se a >= b e a - b forem positivos, obtemos max = a | 0 = a
  • Se a < b e a - b forem negativos, obteremos max = 0 | b = b

Método 2

int max2(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return a ^ ((a ^ b) & mask);
}

Explicação:

  • Explicação de máscara é a mesma que para método 1. Se a > b a máscara é 0x00..00, caso contrário a máscara é 0xFF..FF
  • Se a máscara for 0x00..00, (a ^ b) & mask será 0x00..00
  • Se a máscara for 0xFF..FF, (a ^ b) & mask será a ^ b

Finalmente:

  • Se a >= b, obtemos a ^ 0x00..00 = a
  • Se a < b, obtemos a ^ a ^ b = b
0
Daniel Trugman