По заданным двум целым числам найдите третье целое число, которое отличается от заданных двух без использования if

Вопрос, как упоминалось выше, заключается в следующем: для двух целых чисел x1 и x2 найдите другое целое число x3, которое отличается от x1 и x2 без использования ключевого слова if.

Мое решение основано на побитовых операциях над целыми числами, а также на том факте, что XOR между двумя битами вернет 1, если и только если два бита не равны.

Это решение действительно? Можете ли вы найти лучшее решение? Конечно, соображения времени выполнения и потребление памяти должны быть как можно лучше.

Примечание: троичные операции и сравнения (т.е. -!=, ==) также НЕ допускаются

Заранее спасибо,

Guy.

Мое решение:

int foo(int x1,int x2)
{
    // xor
    int x3 = x1 ^ x2;

    // another xor 
    x3 = x3 ^ x2;

    // not
    x3 = ~x3;

    return x3;  

}
Источник

2 ответа

Решение

Преобразование моих комментариев в ответ:

Что у вас есть ~(x ^ y ^ y)что просто ~xтак что это не сработает, если y = ~x, Вместо этого можно сделать число, отличное от x1 в позиции двойки и отличное от x2 в позиции единиц:

return ~(x1 & 2 | x2 & 1);

(Упрощение от (~x1 & 2) | (~x2 & 1) кредит chux. Спасибо!)

Источник

Быть педантичным, так как они сказали нет if Ключевое слово тогда троицы должны быть честной игрой...

return (x1+1 == x2) ? x1+2 : x1+1;

Конечно, возможно, это обман. Нет проблем, вот версия без троицы:

return x1+1+(x1+1==x2);

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

Обратите внимание, что решение сложения действительно действительно только для целых чисел без знака, так как оно создает потенциал для переполнения со знаком (UB). Если это проблема, вы можете заменить дополнение другой операцией (например, x1^(1+(x1^1==x2)).

Источник
Другие вопросы по тегам