В рамках моих классов CS я недавно завершил довольно популярные задания "Лаборатория данных". В этих назначениях вы должны реализовать простые двоичные операции в C с максимально возможным количеством операций.
Для тех, кто не знаком с "Лабораторией данных", краткий обзор правил:
- Вы не можете вызывать функции, лить или использовать структуры управления (например, если)
- Вы можете назначать переменные без стоимости оператора, однако допускается только int)
- Чем меньше операторов вы используете, тем лучше
- Вы можете предположить sizeof (int) == 32
- Отрицательные числа представлены в 2 дополнениях
Задача состоит в том, чтобы реализовать логический не называемый "bang" (где bang (x) возвращает! x), используя только следующие операторы: ~ и ^ | + < →
Прототип функции определяется как
int bang(int x)
Лучшая реализация, которую я смог найти (используя 5 операторов), была следующей:
return ((x | (~x +1)) >> 31) + 1
Однако, похоже, есть способ сделать это с еще меньшими операторами, так как я нашел веб-сайт результатов [1] из какого-то немецкого университета, где два человека, по-видимому, нашли решение с менее чем 5 операторами. Но я не могу понять, как они это совершили.
[1] http://rtsys.informatik.uni-kiel.de/~rt-teach/ss09/v-sysinf2/dlcontest.html (columnNeg column)
Чтобы уточнить: речь идет не о том, как решить проблему, но о том, как ее решить с меньшими операциями.
