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

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

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

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

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

Например:

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

Ответы

Ответ 1

Предполагая 32-битный беззнаковый int:

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

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

Ответ 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;
}

Ответ 3

Следующий код копирует любой 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

Ответ 4

Для 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.

Ответ 5

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

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

Ответ 6

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