确定点的象限

我需要以更快的方式确定点的象限。我只知道“确定使用符号”的方法。我正在寻找一个好方法，如果有的话。如果没有任何修补程序对我的代码将有所帮助。假设飞机上有四个四边形。我的代码 -确定点的象限

 int x = scan.nextInt() > 0 ? 1 : 0; 
     int y = scan.nextInt() > 0 ? 1 : 0; 
     switch (x) { 
     case 1: 
      switch (y) { 
      case 1: 
       quad = 1; 
       break; 
      case 0: 
       quad = 4; 
       break; 
      } 
      break; 

     case 0: 
      switch (y) { 
      case 1: 
       quad = 2; 
       break; 
      case 0: 
       quad = 3; 
       break; 
      } 
      break; 
     }

来源

2012-03-15 sgowd

这功课吗？你有没有实现“确定使用符号”算法？是否存在性能问题（为什么速度不够快？）。告诉我们你的代码。 – Jesper 2012-03-15 10:43:51

@Jesper不是功课。粘贴我的代码。 – sgowd 2012-03-15 10:44:55

好的，为什么它不够快？ – Jesper 2012-03-15 10:45:44

分支和内存的外观起坐避免的代码片段做微优化时的事情。通过内联汇编，您可以使用CMOV（Conditional MOV）在x86系统上加快速度。 Java的热点编译器也可以被用来指导使用这个指令。但是由于片段非常简单，做太多操作来避免分支或内存查找可能（最终）是失败者。

static int[] QUAD_LUT = new int[]{1, 2, 4, 3}; 
... 
// use the sign bit on the integers 
return QUAD_LUT[ (x >> 31) | ((y >> 30) & 0x2) ]

当你想到的结果你后

x.sign y.sign Quad 
0  0  1 
0  1  4 
1  0  2 
1  1  3

你可以得到公式

(x.sign XOR y.sign + y.sign + y.sign) + 1

所以在Java中

y = y>>31; 
return ((x>>31)^y) + y + y + 1;

编辑只是为人们好奇的内联汇编...

;; NASM/FASM syntax 
;; GetQuadrant(int x, int y) 
;; RETURN [1|2|3|4] in EAX register 
GetQuadrant: 
    MOV  eax, [esp+4] ;; = x 
    MOV  ecx, [esp+8] ;; = y 
    SHR  eax, 31 ;; = >> 31 
    SHR  ecx, 31 ;; = >> 31 
    XOR  eax, ecx ;; = x XOR y 
    LEA  eax, [eax + ecx * 2 + 1] ;; = x + y*2 + 1 
    RET  8 ;; correct stack and return

来源

2012-03-15 14:01:04

相当不错，恭喜！ – PhyBandit 2012-03-15 14:14:10

不错的一个。我没有得到这些运营商的想法。 – sgowd 2012-03-17 11:09:41

这是您的方法。看起来很简单...

getQuadrant(int x, int y) { 
    if (x >= 0) { 
     return y >= 0 ? 1 : 4; 
    } else { 
     return y >= 0 ? 2 : 3; 
    } 
}

来源

2012-03-15 10:47:35 AlexR

这真的比我的简单。但不是更快。 – sgowd 2012-03-15 13:50:59

如果目标是表现，这个答案是不正确的。分支是已知的性能障碍。如果目标是最佳实践/清晰度，这是一个明显的胜利者。 – 2012-03-15 15:01:39

int[] quads = new int[] { 3, 2, 4, 1 }; 

int x = scan.nextInt() > 0 ? 2 : 0; 
int y = scan.nextInt() > 0 ? 1 : 0; 

int result = quads[x + y];

来源

2012-03-15 10:50:29 Jesper

性能明智这是使用2分支和内存查找。使用带有静态“四元组”查找的无分支版本可能会使其成为优化的一般选择。 – 2012-03-15 15:13:08

保持简单！不需要分支机构，位混乱，内存查找，汇编语言或其他复杂性。。

int getQuadrant(int x, int y) { 
    int X = (x >= 0); 
    int Y = (y >= 0); 
    return 3 + X - Y - 2 * X * Y; 
}

（说明鉴于X和Y在我的功能，象限由该二次多项式给出：

1 * X * Y + 2 * (1 - X) * Y + 3 * (1 - X) * (1 - Y) + 4 * X * (1 - Y)

，然后如果你收集的条款和简化，你得到的表达我用。）

来源

2012-03-15 21:08:24

这不是JAVA。我无法初始化int X =（x> = 0）;由于该表达式返回一个布尔值。 – sgowd 2012-03-16 05:11:52

啊，好吧。我认为这种事情通过单独的布尔类型证明了[艾弗森的约定]（http://en.wikipedia.org/wiki/Iverson_bracket）的优点。 – 2012-03-16 09:47:24

我真的很喜欢上面的位旋转的例子 - 但我需要在3D和C ...这么做，以防万一这是有用的。我敢肯定，如果有人需要它，它足够接近转换为java。

int 
point_to_3d_quad (int x, int y, int z) 
{ 
    static int q[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; 

    int X = (x >> ((sizeof(x)*8)-1)) & 1; 
    int Y = ((y >> ((sizeof(y)*8)-1)) & 1) << 1; 
    int Z = ((z >> ((sizeof(z)*8)-1)) & 1) << 2; 

    return (q[X | Y | Z]); 
}

来源

2017-04-08 01:58:54

确定点的象限

回答

相关问题