Reducing number of operations

Question

I have a function to find the max of three numbers, but it uses 24 ops I want to reduce it to 20 ops. Only using bitwise operations.

int maxOfThree(int x, int y, int z) {
int a1 = (x+(~y+1))>>31;
int a2 = (x+(~z+1))>>31;
int a3 = (y+(~z+1))>>31;
return ((~a1&((a2&z)|(~a2&x))) | (a1& ((a3&z)|( ~a3&y)))) ;
}

Would you be allowed to write `~y+1` as `-y`? Because either isn't strictly speaking a bitwise operation - not exactly. — Floris, Mar 04 '14 at 22:52
@Floris The whole thing `(~y+1)` is the bitwise operation to get the negative value of a two's compliment number. — Swiss, Mar 04 '14 at 22:53
@Swiss - I get that; my point was that `+` is no more a bitwise operation than `-`. — Floris, Mar 04 '14 at 22:58
+1 is sort of a special case, one might consider a half add a bitwise op. (It is a logical extension of XOR). Though it is a matter of opinion somewhat. — Vality, Mar 04 '14 at 23:12
possible duplicate of [Maximum of three integers using bitwise operations?](http://stackoverflow.com/questions/21816597/maximum-of-three-integers-using-bitwise-operations) — dawg, Mar 04 '14 at 23:16

Floris · Accepted Answer · 2014-03-04T23:37:42.320

Assuming that your code as written doesn't use any "illegal" operations (i.e. you are OK with +1), then you can write

#include <stdio.h>

int main(void) {
int x, y, z;
int mxy, mxyz;
x = 5;
y = 123; 
z = 9;
mxy = x - ((x - y) & ((x - y) >> 31)); // max(x, y)
mxyz = mxy - ((mxy - z) & ((mxy - z) >> 31));
printf("max is %d\n", mxyz);
}

Only 10 operations. Every - can be replaced with a ~ and +1 adding a further 6 operations. I will leave that as an exercise. Point is - you don't need to evaluate max(x,y) and max(y,z) and max(x,z) separately. max(x,y,z) = max(max(x,y),z)... and that's where your savings come from.

UPDATE using only +1 and bitwise operators:

#include <stdio.h>

int main(void) {
  unsigned int x, y, z, r;
  unsigned int mxy, mxyz;
  unsigned int xmy;
  unsigned int mxymz;

  x = 5;
  y = 123; 
  z = 9;
  xmy = x + (~y+1); // x minus y
  mxy = x + ~(xmy & (xmy >> 31)) + 1; // max(x, y)
  mxymz = mxy + (~z+1); // max(x,y) minus z
  mxyz = mxy + (~(mxymz & (mxymz >> 31))+1); // max(x,y,z)
  printf("max is %d\n", mxyz);
}

Total of 16 operations (plus 3 intermediate assignments to variables, if you're counting those). Using only + ~ >>. I think that counts.

A couple of points:

the hard-wired value 31 really should be sizeof(int) * CHAR_BIT - 1
You should be using unsigned integers since the >>31 operation is not recommended on signed integers (see https://www.securecoding.cert.org/confluence/display/seccode/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands )

A straight `+` or `-` typically aren't considered bitwise operations. Usually `+1` and `-1` are the only exceptions to this rule. — Swiss, Mar 04 '14 at 22:59
Also note that even `+1` and `-1` aren't true bitwise operators. — Swiss, Mar 04 '14 at 23:01
@Swiss - OK I have updated to have only `+` which was an allowed operator (OP didn't say `+1`, just `+`). — Floris, Mar 04 '14 at 23:05

Reducing number of operations

1 Answers1