Нахождение минимального значения между 2 числами без операторов сравнения - PullRequest
Новая
       30

Нахождение минимального значения между 2 числами без операторов сравнения

1 голос
/ 30 мая 2019

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

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

Здесь, если x = 6 и y = 4, x-y = 2 положительно и смещение этого значения 31 раз вправо дает 0. (поскольку знаковый бит равен 0 для + ve чисел), и уравнение становится 

y + ((x-y)&0)

Из приведенного выше уравнения мы получаем y как минимальное значение, которое является истинным.

Но для случая, когда x = 4 и y = 6, x-y = -2 и смещение его 31 раз вправо дает 1, и уравнение становится: 

y + ((x-y)&1)

В соответствии с моим пониманием поразрядно & -2 и 1 становится 0, и уравнение дает o / p как y (6) вместо x (4). Может кто-нибудь объяснить?

Полный код: https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

Спасибо

Ответы [ 3 ]

3 голосов
/ 30 мая 2019

Объяснение на указанном веб-сайте неверно.Когда x < y

(x - y) >> 31 = 0b1...1 (32 ones) (*)

И затем 

y + ((x - y) & 0b1...1) = y + (x - y) = x

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

2 голосов
/ 30 мая 2019

До утверждения нового стандарта представление целых чисел со знаком основано на реализации, а также >> на них (<< - это UB).Предположим, что платформа получила знаковые значения в качестве дополнения к 2, тогда -2 в двоичном виде - это 11111111111111111111111111111110. Сдвиг вправо 31 раз может фактически привести к значению всех установленных битов (что равно -1) или к значению 1, зависит от реализации,Это должно быть <code>static_cast без знака, чтобы быть сдвинутым определенным образом.

2 голосов
/ 30 мая 2019

Это не эффективно и медленнее на многих архитектурах, чем "нормальный" способ.Я должен также упомянуть, что он не читается и очень подвержен ошибкам.

пример: 

int foo(int x, int y) 
{
    return (y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1))));
}

int foo1(int x, int y) 
{
    return x > y ? y : x;
}

и полученный код (ARM Cortex): 

foo:
        sub     r0, r0, r1
        and     r0, r0, r0, asr #31
        add     r0, r0, r1
        bx      lr
foo1:
        cmp     r0, r1
        movge   r0, r1
        bx      lr

илиx86 

foo:
        sub     edi, esi
        mov     eax, edi
        sar     eax, 31
        and     eax, edi
        add     eax, esi
        ret
foo1:
        cmp     edi, esi
        mov     eax, esi
        cmovle  eax, edi
        ret
...