Используя побитовые операторы, найдите логический не эквивалентный

Question

Использование только :

<< >> | ^ & +

Как создать функцию, эквивалентную логическому оператору not (!)?

Прямо сейчас яесть:

int i = (~x + 1) >> 31; 
int j = (x + 1) >> 31; 
i = i | j; 
i = i & 1; 
return i ^ 1;

Работает для всего, но -1.

Answer 1

Я предполагаю, что вы работаете с int 32-битными, подписанными и использующими нотацию дополнения 2. Уникальность числа 0 состоит в том, что ни 0, ни его отрицание не имеют 1 для знаковых битов. Этот код будет работать, если вам будет разрешено использовать оператор отрицания (-):

int not(int x)
{
    return (-x | x) >> 31 & 1 ^ 1;
}

Вы не можете использовать минус, но это нормально, потому что для всех x мы знаем, что -x равно ~x + 1, что равно (x ^ -1) + 1. Вот как работает нотация дополнения 2. Итак, окончательный ответ:

int not(int x)
{
    return ( (x^-1)+1 | x ) >> 31 & 1 ^ 1;
}

РЕДАКТ. 1: Хорошо, вот версия «ANSI» функции, которая не делает никаких предположений о размере int и не полагается на неопределенное поведение смещения вправо подписанного int. У меня это работает в MinGW:

int not(int x)
{
    unsigned int y = x;
    return (( ((y^-1)+1) | y ) >> (sizeof(x)*8-1)) ^ 1;
}

Answer 2

Вид "обмана", но:

bool logicalNot(int i)
{
    return((bool)i ^ true);
}

Я предполагаю, что в правилах нет ничего о компоновке функций / приведении типов / неявных преобразованиях типов?

Answer 3

Предполагая, что x является 32-битным значением без знака:

x = x | (x >> 1)
x = x | (x >> 2)
x = x | (x >> 4)
x = x | (x >> 8)
x = x | (x >> 16)

В этот момент, если x был 0, тогда это все еще 0. Если у него было ненулевое значение, он теперь имеет битшаблон 111 .... 111.

С представлением в два дополнения вы можете теперь просто добавить 1 и получить желаемый результат:

x = x + 1

Это решение предполагает довольно много о целых числахпредставление, типы и т. д.

(Конечно, приведенный выше код не является допустимым кодом C).