CODEWITHSUNDEEP
cbit-manipulation
user3316874
user3316874

Reputation: 223

Reducing number of operations

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)))) ;
}

Upvotes: 2

Views: 123

Answers (1)

Floris
Floris

Reputation: 46365

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:

  1. the hard-wired value 31 really should be sizeof(int) * CHAR_BIT - 1
  2. 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 )

Upvotes: 2

Related Questions