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

Question

Найти максимум двух чисел. Вы не должны использовать 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;  
}

Answer 1

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, если число отрицательное. Кроме того, большинство целых 32-битных. (c >> 31) сдвигает число на 31 бит вниз, оставляя старший бит числа в месте для младшего бита. Следующий шаг - взять это число и сложить его с 1 (двоичное представление которого равно 0 везде, кроме последнего бита) стирает все старшие биты и просто дает вам младший бит. Поскольку младший бит c >> 31 является старшим битом c, это означает, что старший бит c считывается как 0 или 1. Поскольку старший бит равен 1, тогда как 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

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

Answer 2

Вот и мы: (a + b) / 2 + |a - b| / 2

Answer 3

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

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)

Источник: Бит Тиддлинг Хаки от Шона Эрона Андерсона

Answer 4

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

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

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

Если мы будем использовать 9 и 11 в качестве наших чисел, мы получим (sqrt (121 + 81 - 198) + 11 + 9) / 2 = (sqrt (4) + 20) / 2 = 22/2 = 11

Answer 5

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

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

Answer 6

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

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

Answer 7

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

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

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

Обратите внимание, что:

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

Answer 8

Вот как я думаю, я бы сделал эту работу.Это не так легко читается, как хотелось бы, но когда вы начинаете с того, «как я могу сделать 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-битных чисел. Во-вторых, с большинством компиляторов мы можем ожидать, что все умножения произойдут во время компиляции, поэтому все, что остается во время выполнения, - это тривиальные битовые манипуляции (вычитание и сдвиг), за которыми следуют загрузка и возврат.Короче говоря, это почти наверняка будет довольно быстро, даже на самом маленьком микроконтроллере, где оригинальное использованное умножение должно было произойти во время выполнения, так что, хотя это, вероятно, довольно быстро на настольном компьютере, оно часто будет довольномедленнее на маленьком микроконтроллере.

Answer 9

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

c - ab.если с отрицательный, а= b, так что max это a - 0 * c = a.Если с равен 1, это означает, что

Answer 10

Функция 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

---

Другой способ -

int getMax(int a, int b){
    int i[] = {a, b};
    return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ];
}