c - 减少操作次数

Question

我有一个函数可以查找三个数字的最大值，但它使用 24 次操作，我想将其减少到 20 次操作。仅使用按位运算。

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

Answer 1

假设您编写的代码不使用任何“非法”操作(即您可以使用+1)，那么您可以编写

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

只有 10 次操作。每个 - 都可以替换为 ~ 和 +1，另外添加 6 个操作。我将把它作为练习。要点是 - 您不需要评估 max(x,y) 和 max(y,z) 和 max(x,z) > 分别。 max(x,y,z) = max(max(x,y),z)...这就是您的节省的来源。

更新仅使用+1和按位运算符:

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

总共 16 个操作(加上 3 个对变量的中间赋值，如果您计算的话)。仅使用 + ~ >>。我认为这很重要。

几点:

1. 硬连线值31确实应该是sizeof(int) * CHAR_BIT - 1
2. 您应该使用无符号整数，因为不建议对有符号整数执行 >>31 运算(请参阅 https://www.securecoding.cert.org/confluence/display/seccode/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands )