Как это побитовое выражение помогает найти минимум и максимум между двумя целыми числами? - PullRequest
Новая
       14

Как это побитовое выражение помогает найти минимум и максимум между двумя целыми числами?

3 голосов
/ 19 марта 2019

https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

Я пытался найти альтернативные способы нахождения максимума и минимума между двумя целыми числами и наткнулся на следующий код, который используется для операции. Может кто-нибудь, пожалуйста, проясните работу и рольпобитовый оператор в коде: 

/*Function to find minimum of x and y*/
int min(int x, int y) 
{ 
    return y ^ ((x ^ y) & -(x < y)); 
} 

/*Function to find maximum of x and y*/
int max(int x, int y) 
{ 
    return x ^ ((x ^ y) & -(x < y));  
}

Ответы [ 2 ]

4 голосов
/ 19 марта 2019 
return y ^ ((x ^ y) & -(x < y));

-(x < y) будет 0, если x >= y, и -1 (то есть, int со всеми установленными битами), если x < y.Обратите внимание, что foo & -1 == foo и foo & 0 == 0 для всех foo.Так что если x < y, мы получим y ^ x ^ y, что равно x, потому что y ^ y отменяет.И в противном случае мы получаем y ^ 0, что y.Таким образом, мы получаем x, если x < y и y в противном случае, что именно то, что вы хотите от функции с именем min.

Для max это то же самое, за исключением того, что мы возвращаемy если x < y и x в противном случае.

2 голосов
/ 19 марта 2019

Сначала давайте посмотрим на эту часть: 

-(x < y)

Если условие истинно, т. Е. Если x меньше y, то выражение в скобках равно 1, а все выражение равно -1,Если условие ложно, то выражение имеет значение 0.

Теперь давайте рассмотрим его в контексте подвыражения следующего уровня: 

((x ^ y) & -(x < y))

Исходя из вышеизложенного условия, это будетуменьшите до одного из следующего: 

((x ^ y) & 0)     // x is larger or equal
((x ^ y) & -1)    // y is larger

Выполнение побитового И с 0 приводит к тому, что все биты результата равны 0, поэтому первое выражение будет 0. Значение -1, предполагая представление дополнения до двух,все биты установлены в 1. Таким образом, выполнение побитового И с -1 приведет к значению другого операнда.

Итак, теперь рассмотрим полное выражение для max: 

x ^ ((x ^ y) & -(x < y))

Это означает: 

x ^ (0)        // x is larger or equal
x ^ (x ^ y)    // y is larger

В первом случае выполнение XOR с 0 приводит к значению другого операнда, поэтому окончательный результат равен x.Во втором случае ^ является ассоциативным, так что вы можете смотреть на него как (x ^ x) ^ y. Если XOR для числа с самим собой, то получится 0, а XOR для 0 с y даст вам y.

. *Функция 1030 * работает аналогично с y вместо x для первого операнда: 

y ^ (0)        // x is larger or equal
y ^ (x ^ y)    // y is larger

Это даст противоположный результат max.

...