Объясните этот фрагмент, который находит максимум двух целых чисел без использования if-else или любого другого оператора сравнения?



найти максимум из двух чисел. Вы не должны использовать if-else или любой другой оператор сравнения. Я нашел этот вопрос на онлайн-доске объявлений, поэтому я подумал, что должен спросить в StackOverflow



пример
Вход: 5, 10
Выход: 10



Я нашел это решение, может кто-нибудь помочь мне понять эти строки кода



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

19 ответов:

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

давайте разберем это. Эта первая строка кажется, что это просто - она хранит разницу a и b. Это значение отрицательно, если a < b и неотрицательный в противном случае. Там на самом деле ошибка здесь - если разница чисел a и b настолько большой, что он не может поместиться в целое число, это приведет к неопределенному поведению - ой! Так что давайте предположим, что здесь этого не происходит.

в следующей строке, которая это

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

идея в том, чтобы проверить, если значение c отрицательный. Практически на всех современных компьютерах числа хранятся в формате два, в котором старший бит числа равен 0, если число положительное и 1, если число отрицательное. Кроме того, большинство ints-это 32 бита. (c >> 31) сдвигает число вниз на 31 бит, оставляя самый высокий бит числа в месте для самого низкого бита. Следующий шаг взять этот номер и Андинг он с 1 (чье двоичное представление равно 0 везде, кроме последнего бита) стирает все более высокие биты и просто дает вам самый низкий бит. С самого нижнего бита c >> 31 это самый высокий бит c, это читает самый высокий бит c 0 или 1. Так как самый высокий бит равен 1 iff c это 1, это способ проверить, является ли c отрицательно (1) или положительно (0). Сочетая это рассуждение с вышеизложенным,k 1, Если a < b и 0 иначе.

последний шаг, чтобы сделать это:

int max = a - k * c;

если a < b, потом k == 1 и k * c = c = a - b и так

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

, который является правильным Макс, начиная с a < b. В противном случае, если a >= b, потом k == 0 и

a - k * c = a - 0 = a

что также является правильным макс.

поехали: (a + b) / 2 + |a - b| / 2

используйте побитовые хаки

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

если вы знаете, что INT_MIN <= x - y <= INT_MAX, тогда вы можете использовать следующее, Что быстрее, потому что (x - y) только должен быть оценен один раз.

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

источник : бит вертя хаки Шон Эрон Андерсон

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

это основано на той же технике, как Майк.решение длд-х, но здесь менее "очевидно" то, что я делаю. Операция " abs " выглядит так, как будто вы сравниваете знак чего-то, но я здесь использую тот факт, что sqrt() всегда будет возвращать вам положительный квадратный корень, поэтому я квадрат (a-b) записываю его полностью, а затем снова квадратно укореняю его, добавляя a+b и деля на 2.

вы увидите, что это всегда работает: например, пример пользователя 10 и 5 Вы получаете sqrt(100 + 25 - 100) = 5 затем добавьте 10 и 5 дает вам 20 и разделить на 2 дает вам 10.

Если мы используем 9 и 11 числа, мы получим (корень(121 + 81 - 198) + 11 + 9)/2 = (Функция sqrt(4) + 20) / 2 = 22/2 = 11

самый простой ответ ниже.

#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);
}
int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

такое решение позволяет избежать умножения. m будет либо 0x00000000, либо 0xffffffff

используя идею сдвига, чтобы извлечь знак, опубликованный другими, вот еще один способ:

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

это помещает два числа в массив с максимальным числом, заданным элементом массива, индекс которого является знаковым битом разности между двумя числами.

отметим, что:

  1. разница (a - b) может переполниться.
  2. Если числа без знака и >> оператор относится к логическое сдвиг вправо, то & 1 - это лишнее.

вот как я думаю, я бы сделал эту работу. Это не так читаемо, как вам может понравиться, но когда вы начинаете с "как мне сделать X без использования очевидного способа выполнения X, вы должны ожидать этого. Теоретически это тоже дает некоторую переносимость, но вам нужно будет найти довольно необычную систему, чтобы увидеть проблему.

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

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

Это имеет некоторые преимущества по сравнению с показанным на вопрос. Прежде всего, он вычисляет правильный размер сдвига, а не жестко закодирован для 32-битного значения типа int. Во-вторых, с большинством компиляторов мы можем ожидать, что все умножение произойдет во время компиляции, поэтому все, что осталось во время выполнения, - это тривиальная битовая манипуляция (вычитание и сдвиг) с последующей загрузкой и возвратом. Короче говоря, это почти наверняка будет довольно быстро, даже на самом маленьком микроконтроллере, где первоначально использовалось умножение, которое должно было произойти во время выполнения, поэтому, хотя это, вероятно, довольно быстро на настольной машине, это часто будет немного медленнее на маленьком микроконтроллере.

вот что делают эти строки:

c - это a-b. если c отрицательно, a

k-32-й бит c, который является знаковым битом c (предполагая 32-разрядные целые числа. Если сделано на платформе с 64-битными целыми числами, этот код не будет работать). Он сдвинут 31 бит вправо, чтобы удалить самый правый 31 бит, оставив знаковый бит в самом правом месте, а затем anding его с 1, чтобы удалить все биты влево (которые будут заполнены 1s, если c отрицательно). Так что k будет 1, Если C-это отрицательное и 0, если c является положительным.

тогда max = a-k * c. если c равно 0, это означает a>=b, поэтому max - a-0 * c = a. если c равно 1, это означает, что a

в целом, это просто использование знакового бита разницы, чтобы избежать использования больше или меньше операций. Если честно, немного глупо говорить, что этот код не использует сравнение. c-результат сравнения A и B. Код просто не использовать оператор сравнения. Вы можете сделать то же самое во многих кодах сборки, просто вычитая числа, а затем прыгая на основе значений, установленных в регистре состояния.

Я должен также добавить, что все эти решения, при условии, что два числа являются целыми числами. Если они являются поплавками, двойниками или чем-то более сложным (BigInts, Rational numbers и т. д.) тогда вам действительно нужно использовать оператор сравнения. Бит-трюки обычно не делают для них.

функция getMax () без какой-либо логической операции -

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

объяснение:

давайте разбить "Макс" на куски,

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

Итак, функция должна выглядеть так-

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

теперь

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] )

в целочисленном положительном числе Первый БИТ (знаковый бит) -0; в отрицательном это -1. Путем сдвига битов вправо ( > > ) первый бит может быть захвачен.

во время сдвига вправо пустое пространство заполняется битом знака. Так что 01110001 >> 2 = 00011100, в то время как 10110001 >> 2 = 11101100.

в результате для 8-битного сдвига числа 7 бит либо произведет- 1 1 1 1 1 1 1 [0 или 1] для отрицательных, или 0 0 0 0 0 0 0 [0 или 1] для положительных.

теперь, если или операция выполняется с помощью 00000001 (= 1), негативные количество выходов -11111111 (= -1), и положительные- 00000001 (= 1).

и

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 )

наконец,

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2

static 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];

    }

Если B > A, то (А-Б) будет отрицательным, знак будет возвращать -1, добавив 1 мы получаем индекс 0, который является B, если B=A, то А-B будет 0, +1 даст 1 индекс, поэтому она не имеет значения, если мы возвращаемся A или B, если А > B, то a-b будет положительной и знак вернется 1, добавление 1 мы получаем индекс 2, где хранится.

#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");
}

код, который я предоставляю для нахождения максимума двух чисел, числа могут быть любого типа данных(целое число, плавающая). Если входные числа равны, то функция возвращает число.

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 ));
}

описание

  • первое, что функция принимает аргументы как double и имеет тип возврата как double. Причина этого заключается в том, что для создания одной функции можно найти максимум для всех типов. Когда целочисленный тип числа предоставляются или один является целым числом, а другой-плавающей точкой, то также из-за неявного преобразования функция может быть использована для поиска max для целых чисел также.
  • основная логика проста, скажем, у нас есть два числа a & b, Если a-b>0(т. е. разница положительна), то a максимальна иначе, если a-b==0, то оба равны и если a-b
  • знаковый бит сохраняется как самый значительный бит(MSB) в памяти. Если ГРЩ расположен в 1 и наоборот. Чтобы проверить, является ли MSB 1 или 0, мы сдвигаем MSB в позицию LSB и побитово & с 1, если результат равен 1, то число-ve else no. это +вэ. Этот результат получается утверждением:

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

здесь, чтобы получить знаковый бит от MSB до LSB, мы справа сдвигаем его на K-1 бит(где k-количество бит, необходимых для сохранения целого числа в памяти, которое зависит от типа системы). Здесь k= sizeof (int) * 8 as sizeof () дает количество байтов, необходимых для сохранения целого числа, чтобы получить no. из битов мы умножаем его на 8. После правого сдвига мы применяем побитовое & с 1, чтобы получить результат.

  • теперь после получения результата (предположим, что это r) как 1 (для-ve diff) и 0(для +ve diff) мы умножаем результат на разность двух чисел, логика дается следующим образом:

    1. если a>b, то a-b>0 т. е. равно +ve, поэтому результат 0 (т. е. r=0). Итак, a-(a-b)*r => a-(a-b)*0, что дает 'a' как максимум.
    2. если a a-(a-b)*1 => a-a+b =>b , что дает 'b' как максимум.
  • теперь осталось два пункта 1. использование цикла while и 2. почему я использовал переменную 'int_diff' в качестве целого числа. Чтобы правильно ответить на эти вопросы, мы должны понять некоторые моменты:

    1. плавающий тип значения не могут использоваться в качестве операнда для побитовых операторов.
    2. по вышеуказанной причине нам нужно получить значение в целочисленном значении, чтобы получить знак различия с помощью побитовых операторов. Эти две точки описывают необходимость переменной 'int_diff' как целочисленного типа.
    3. теперь предположим, что мы находим разницу в переменной 'diff' теперь есть 3 возможности для значений 'diff' независимо от знака этих значений. (ля.) |diff / >=1, (b). 0
    4. когда мы присваиваем двойное значение целочисленной переменной, десятичная часть теряется.
    5. для случая (a) значение 'int_diff' >0 (т. е.,1,2,...). Для двух других случаев int_diff=0.
    6. условие (temp_diff-int_diff) / / 0.0 проверяет, если diff==0, так что оба числа равны.
    7. если diff!=0 затем мы проверяем, является ли int_diff|0 истинным, т. е. случай (b) истинен
    8. в то время как цикл, мы пытаемся получить значение int_diff как ненулевые, так что значение int_diff также получает знак дифференциала.

вот пара бит-сложа методы для получения максимального из двух интегральных значений:

Способ 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);
}

объяснение:

  • (a - b) >> SIGN_BIT_SHIFT - If a > b затем a - b является положительным, таким образом знак бит 0, а маска-это 0x00.00. В противном случае, a < b так a - b отрицательное, то бит знака равен 1 и после сдвига, мы получаем маску 0xFF..FF
  • (a & ~маска) - Если маска 0xFF..FF, потом ~mask и 0x00..00 и тогда это значение 0. В противном случае, ~mask и 0xFF..FF и значение a
  • (b & mask) - если маска 0xFF..FF, потом b. В противном случае, mask и 0x00..00 и значение 0.

и наконец:

  • если a >= b затем a - b - положительный, мы получаем max = a | 0 = a
  • если a < b затем a - b отрицательно, мы получаем max = 0 | b = b

Способ 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);
}

объяснение:

  • Маска объяснение такое же, как для Способ 1. Если a > b маска 0x00..00, в противном случае маска 0xFF..FF
  • если маска 0x00..00, потом (a ^ b) & mask и 0x00..00
  • если маска 0xFF..FF, потом (a ^ b) & mask и a ^ b

и наконец:

  • если a >= b, мы получить a ^ 0x00..00 = a
  • если a < b, мы получим a ^ a ^ b = b

логика, описанная в задаче, может быть объяснена так, как если бы 1-е число было меньше, то 0 будет вычитаться, иначе разница будет вычитаться из 1-го числа, чтобы получить 2-е число. Я нашел еще одно математическое решение, которое, я думаю, немного проще понять эту концепцию.

рассматривая a и b как заданные числа

c=|a/b|+1;
d=(c-1)/b;
smallest number= a - d*(a-b);

опять же, идея состоит в том, чтобы найти k, который увядает 0 или 1 и умножить его с разностью двух чисел.И напоследок это число должно быть вычитается из 1-го числа, чтобы получить меньшее из двух чисел. P. S. Это решение будет не в случае 2-го числа равна нулю

int a=151;
int b=121;
int k=Math.abs(a-b);
int j= a+b;
double k1=(double)(k);
double j1= (double) (j);
double c=Math.ceil(k1/2) + Math.floor(j1/2);
int c1= (int) (c);
System.out.println(" Max value = " + c1);

(a / b) * b + (b/a) * a - (a/b)*(b / a)*a + (abs(a - b) % a) % b

есть один способ

 public static int Min(int a, int b)
  {
   int dif = (int)(((uint)(a - b)) >> 31);
   return a * dif + b * (1 - dif);
  }

и

return (a>=b)?b:a;

думаю, мы можем просто умножить числа с их побитовыми сравнениями, например:

int max=(a>b)*a+(a<=b)*b;

Comments

    Ничего не найдено.