Geek asks and answers

Test if fixed dial is equal without branching

I have a set of integers (x, y, z) and a function that takes 3 integers (u, v, w). How to check if (x, y, z) == (u, v, w)? Naive way:

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

Does anyone know of some smart bit operations / arithmetic to do the same?

Edit: I can assume that neither (x, y, z) nor (u, v, w) contain duplicates.

+3
source share
5 answers

In this case, you can replace logical operations with bitwise operations to eliminate branching:

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

, , .

+3

, unsigned .

+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, .

+2

C .

-, CMPXCHG.

0

, "" , (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)));

a >

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

Some processors have non-branching instructions "min" and "max" that allow you to execute

  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);
0
source

More articles:


All Articles