Реализация логического отрицания только с побитовыми операторами (кроме!)

Question

~ & ^ | + << >> - единственные операции, которые я могу использовать

Прежде чем я продолжу, это домашний вопрос, я застрял в нем очень долго.

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

Для записи: я также не могу использовать условные выражения, циклы, == и т. Д., Только функции (побитовые), которые я упомянул выше.

Например:

!0 = 1
!1 = 0
!anything besides 0 = 0

Answer 1

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

(((x>>1) | (x&1)) + ~0U) >> 31

должен сделать трюк

Answer 2

Предполагая, что x подписано, необходимо вернуть 0 для любого числа, отличного от нуля, и 1 для нуля.

Сдвиг вправо на целое число со знаком обычно является арифметическим сдвигом в большинстве реализаций (например, бит знака копируется). Поэтому смещение вправо x на 31 и его отрицание на 31. Одно из этих двух будет отрицательным числом, и поэтому смещение вправо на 31 будет 0xFFFFFFFF (конечно, если x = 0, тогда правое смещение будет производить 0x0, что вы хочу). Вы не знаете, является ли x или его отрицание отрицательным числом, просто «или» их вместе, и вы получите то, что хотите. Затем добавьте 1 и ваш товар.

реализация:

int bang(int x) {
    return ((x >> 31) | ((~x + 1) >> 31)) + 1;
}

Answer 3

Для 32-разрядного целого числа со знаком x

// Set the bottom bit if any bit set.
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

x ^= 1;   // Toggle the bottom bit - now 0 if any bit set.
x &= 1;   // Clear the unwanted bits to leave 0 or 1.

Answer 4

Следующий код копирует любой 1 бит во все позиции.Это сопоставляет все ненулевые значения с 0xFFFFFFFF == -1, оставляя 0 на 0.Затем он добавляет 1, сопоставляя -1 с 0 и 0 с 1.

x = x | x << 1  | x >> 1
x = x | x << 2  | x >> 2
x = x | x << 4  | x >> 4
x = x | x << 8  | x >> 8
x = x | x << 16 | x >> 16

x = x + 1

Answer 5

Вы можете просто сделать ~ x & 1, потому что это дает 1 для 0 и 0 для всего остального

Answer 6

Предположим, например, 8-битный тип без знака:

~(((x >> 0) & 1)
| ((x >> 1) & 1) 
| ((x >> 2) & 1)
...
| ((x >> 7) & 1)) & 1