Проверить, равен ли фиксированный набор без ветвления

Question

У меня есть набор целых чисел (x, y, z) и функция, которая принимает 3 целых числа (u, v, w).Как я могу проверить, что (x, y, z) == (u, v, w)?Наивный способ:

bool match = (x == u || x == v || x == w) && (y == u || y == v || y== w) && (z == u || z == v || z == w);

Кто-нибудь знает какие-нибудь умные битовые операции / арифметику для того же?1007 *

Редактировать: я могу предположить, что ни (x, y, z), ни (u, v, w) не содержат дубликатов.

Answer 1

В этом случае вы можете заменить логические операции побитовыми операциями для устранения ветвления:

bool match = (x == u | x == v | x == w)
           & (y == u | y == v | y == w)
           & (z == u | z == v | z == w);

Однако вам придется измерить эффект производительности, чтобы увидеть, будет ли он быстрее или медленнее.

Answer 2

Если a и b одинаковы, то a^b равно нулю. Таким образом, !(a^b) не равен нулю только тогда, когда a и b одинаковы. Предположим, что ваша платформа может делать логическое «не» без ветки, поэтому вы можете проверить, является ли a членом (u, v, w) с одной веткой, используя:

if(!(a^u) | !(a^v) | !(a^w))

И, следовательно, все ли (x, y, z) являются членами (u, v, w), используя:

if(
    (!(a^u) | !(a^v) | !(a^w))) &
    (!(b^u) | !(b^v) | !(b^w))) &
    (!(c^u) | !(c^v) | !(c^w))))

т.е. просто делаю бит по разным результатам и опять же только одну ветку.

Если вашей платформе требуется ветвь для выполнения !, например, если он выполняется по существу как a ? 0 : -1, то это десять условий и не лучше, чем наивное решение.

Answer 3

Вы можете заранее устранить кучу неравных векторов, преобразовав их в unsigned и сравнив суммы перед выполнением реального теста.

Answer 4

Как указано в комментариях, ваш «наивный» путь совпадает, когда все элементы в (x, y, z) содержатся в наборе (u, v, w).Если вы действительно хотите проверить, эквивалентны ли наборы, вы, вероятно, захотите

 (x==u && ((y==v && z==w) || (y==w && z==v))) ||
 (y==u && ((z==v && x==w) || (x==w && z==v))) ||
 (z==u && ((x==v && y==w) || (y==w && x==v)));

. Вы можете быстро отфильтровать множество несовпадений с помощью

  bad = (x+y+z) - (u+v+w);

Некоторые процессоры имеютразветвление инструкций 'min' и 'max', которые позволят вам выполнить

  a = min(x,y)
  b = max(x,y)
  c = min(b,z)
  x = min(a,c)
  y = max(a,c)
  z = max(b,z) 
  //repeat sorting sequence for u,v,w
  match = (x==u)&(y==v)&(z==w);

Answer 5

В C нет способа сделать это без ветвления.

Если вы готовы к inline-сборке, вы можете сделать это с помощью некоторых CMPXCHG инструкций.