Условное использование побитовых операторов

Question

Как условный оператор представляется с помощью побитовых операторов?

Это вопрос домашнего задания, в котором я должен реализовать условный оператор, используя только побитовые операции. Было бы просто, если бы if операторы были разрешены, однако это должны быть строго побитовые операторы.

Можно использовать только операторы !, ~, &, ^, |, +, >> и <<. if операторы или циклы не могут быть использованы.

Функция принимает три целых числа и работает так же, как обычный условный оператор. Первый аргумент оценивается как ноль или не ноль. Если первый аргумент равен нулю, возвращается второй аргумент. Если первый аргумент не равен нулю, возвращается третий аргумент.

Я надеялся, что для этого будет простой алгоритм. Любые идеи о том, с чего начать, будут очень полезны.

Answer 1

Разрешены ли сдвиги как побитовые операторы? Разрешены ли арифметические операторы?

Ваше редактирование не совсем ясно, но я предполагаю, что вам нужно реализовать эквивалент

a ? b : c

, где a, b и c - целые числа. Это в свою очередь эквивалентно

a != 0 ? b : c

Один из способов добиться этого - найти способ превратить ненулевое значение a в битовую комбинацию из всех единиц, используя только побитовые операторы. Если мы выясним, как это сделать, остальное будет легко. Теперь я не сразу помню какие-то хитрые трюки, которые могли бы это сделать (я думаю, они существуют), и я точно не знаю, какие операторы разрешены, а какие нет, поэтому сейчас я просто буду использовать что-то вроде

a |= a >> 1; a |= a >> 2; a |= a >> 4; a |= a >> 8; a |= a >> 16;
a |= a << 1; a |= a << 2; a |= a << 4; a |= a << 8; a |= a << 16;

Для 32-разрядного целочисленного типа, если (и только если) был установлен хотя бы один бит в исходном a, приведенное выше должно привести ко всем битам a, установленным в 1. (Предположим, что мы работаем с целыми числами без знака, чтобы избежать проблем, связанных со смещением значений со знаком). Опять же, должен быть более умный способ сделать это, я уверен. Например: a = !a - 1, но я не знаю, разрешены ли ! и -.

Как только мы это сделаем, исходный условный оператор станет эквивалентным

(a & b) | (~a & c)

Готово.

Answer 2

Это не так, в основном. Условный оператор будет оценивать только один второго или третьего операнда; побитовые операторы всегда оценивают оба операнда.

Я не думаю, что действительно имеет смысл думать об условном операторе в терминах побитовых операторов, чтобы начать с ... например, если второй и третий операнды являются типами указателей, вам не хотелось бы думать те с точки зрения побитовых операций, не так ли? Относитесь к условному оператору отдельно к побитовым операторам - вы не будете делать себе одолжение, пытаясь объединить их.

Answer 3

Я думаю, что ОП ищет способ выразить вещи, которые обычно требуют условного выражения без ответвлений.Например (при условии, что unsigned x,y,z; и x ограничены INT_MAX):

if (x>2) y+=z;

можно выразить как:

y += z & -(2-x >> sizeof(unsigned)*CHAR_BIT-1);

Этот пример приходит на ум, потому что я 'мы использовали его в «бинарной сортировке без разветвлений» в ряде случаев.Когда размер искомого массива постоянен, это позволяет полностью развернуть цикл поиска в последовательность операций без ветвей и компилировать всего несколько кодов операций за шаг.Те, кто возражает против написания «ассемблера в C», могут предпочесть, чтобы оно было написано:

y += (x>2) ? z : 0;

и надеяться, что компилятор сгенерирует эквивалентную битовую маску или инструкцию cmov.: -)

Answer 4

Если вы ссылаетесь на троичный оператор выбора, это может быть представлено с использованием побитовых операций, но только в определенных случаях (на самом деле, это оптимизация для использования побитовых операций в некоторых случаях).Например: (getsomevalue() == 1) ? somepointer : NULL; может быть представлен как somepointer & ~((unsigned)(getsomevalue()) - 1); при условии, что getsomevalue() возвращает только 1 или 0 (он же BOOL)

Answer 5

На самом базовом уровне это становится электроникой. Смотрите это . Я не могу придумать ни одного другого приложения для вашего вопроса.