Определение, подходит ли Int к короткому в C, используя побитовые операторы

Question

Мне поручено создать функцию, которая возвращает, подходит ли int x к короткому в C (верните 1, если это так, 0 в противном случае).Обычно это довольно простое решение, но я вынужден использовать только следующие побитовые операторы :!~ & ^ |+ << >>.

Вот еще несколько правил:

• Мне разрешено использовать не более 8 из этих операторов.

• Внешние библиотеки не должны быть включены.

• Мне не разрешено использовать какие-либо условные операторы (поэтому нет ifs, whiles и т. Д.).

• Единственные переменные, с которыми я могу работать, это переменные типа int, и я не могу определить константы, такие как 0x0000ffff.Тем не менее, я могу использовать 0x0 и 0xff.

• Можно с уверенностью предположить, что 32-разрядные биты и 16-битные шорты.

Я понимаюОсновные функциональные возможности этих операторов, но я запутался в логике реализации.Есть идеи?

Answer 1

Предполагая, что 2 дополнения, ваша оригинальная идея проверить, что все старшие, но 15 битов - все 0 или все 1. Работает.

11111111 11111111 1xxxxxxx xxxxxxxx /* for negative 16 bits int */
00000000 00000000 0xxxxxxx xxxxxxxx /* for positive 16 bits int */

Принимая арифметическое смещение вправо, вы можете сместить вправо на 15, чтобы устранитьнеизвестные биты, тогда останутся только 1 с или 0 (если он умещается в 15 битах)

Таким образом, тогда x>>15 должно быть либо 0, либо -1.
Если это 0, то! (x>> 15) верно.
Если оно равно -1, то! (~ (X >> 15)) верно.
Таким образом, вы можете проверить !(x>>15) | !(~(x>>15))
Или вы также можете написать это так: !(x>>15) | !(~x>>15)

Обратите внимание, что вышеприведенные выражения не предполагают 32 бита x, а также будут работать для тестирования, если int64 поместится в int16 ...

. Есть много других способов...
Поскольку вы также можете использовать +, (x>>15)+1 равен 0 или 1.
Затем вы можете очистить последний бит с помощью: ((x>>15)+1)>>1.
x вписывается в 16-битное int, если выражение вышевсе 0 (ложь), поэтому вы хотите:

! (((x>>15)+1)>>1)

До вас, чтобы найти больше выражений ...

Answer 2

Предположим, что два дополнения, арифметическое смещение вправо, смещение влево, отбрасывающее переполненные биты, и 32-битное int, тогда:

x<<16>>16 ^ x

равно нулю тогда и только тогда, когда вписывается x16-битный short.

Так как нас просят вернуть ноль для "не подходит" и один для "не подходит", мы можем вернуть:

! (x<<16>>16 ^ x)

Доказательство:

Если x подходит для short, то x • 2 ¹⁶ подходит для int, поэтому x<<16 создает это без переполнения, и x<<16>>16восстанавливает x (поскольку арифметическое смещение вправо, при котором удаляются только нули, фактически является делением без остатка), после которого x ^ x равно нулю.

Если x превышает короткое, то x<<16 переполняется (что мы предполагаем, приводит к отбрасыванию старших бит).Кроме того, его значение является одним из значений, полученных y<<16 для некоторого y, что является коротким.Тогда x<<16>>16 должно выдавать то же значение, что и y<<16>>16, то есть y, которое отличается от x, и, следовательно, x<<16>>16 ^ x не может быть нулем.