动态查找矩形的边
Dynamically Find the Edge of a Rectangle
我有 2 个 2D 点,它们挤在一起形成一个数组:int square[4]
。这四个数字被解释为具有平行于 X 轴的水平线和平行于 Y 轴的垂直线的矩形的定义。然后数组的元素分别定义:
- 左边的X坐标
- 底边的Y坐标
- 右边缘的X坐标
- 顶边的Y坐标
我已经在这个enum
中定义了绕组顺序:
enum WindingOrder {
BOTTOM = 0,
RIGHT,
TOP,
LEFT
};
我的代码的最小、完整、可验证的示例是,我得到了一个输出第二数组:int output[4]
和一个输入 WindingOrder edge
。我需要按如下方式填充 output
:
switch(edge) {
case BOTTOM:
output[0] = square[0]; output[1] = square[1]; output[2] = square[2]; output[3] = square[1];
break;
case RIGHT:
output[0] = square[2]; output[1] = square[1]; output[2] = square[2]; output[3] = square[3];
break;
case TOP:
output[0] = square[2]; output[1] = square[3]; output[2] = square[0]; output[3] = square[3];
break;
case LEFT:
output[0] = square[0]; output[1] = square[3]; output[2] = square[0]; output[3] = square[1];
break;
}
我没有嫁给特定的 WindingOrder
安排,我也不关心 ouptut
中的点的顺序,所以如果改变这些可以解决这个问题,我会失望的。我想知道的是我可以在 for
循环中构造 square
索引以分配给 output
, 没有 和 if
/case
/三元语句(换句话说使用按位运算)?
所以我想,给定 int i = 0
和 WindingOrder edge
对它们进行按位运算以找到:
do {
output[i] = array[???];
} while(++i <= LEFT);
编辑:
我收到了很多静态数组的答案(我认为这是解决这个问题的最佳方法,所以我给了 +1)。但作为一个逻辑问题,我很好奇可以采用多少位运算来动态查找给定边的元素。因此,例如,在给定任意 edge
和 i
的情况下,该函数的主体应该如何编写:int getIndex(int i, int edge)
这是未经测试的,在某些细节上可能存在小错误,但总体思路应该可行。
将数组复制到输出将使用索引 {0,1,2,3}
。要获得特定优势,您必须对索引进行一些转换:
changed_pos changed_to
RIGHT : {2,1,2,3} 0 2
TOP : {0,3,2,3} 1 3
LEFT : {0,1,0,3} 2 0
BOTTOM: {0,1,2,1} 3 1
所以基本上你必须为你的绕组的具体位置添加2 mod 4
。
所以(就像我说的未经测试的)剪断可能看起来像这样
for (size_t i=0; i<4; ++i) {
output[i] = array[(i+(i==edge)*2)%4];
}
如果比较结果为真,则将 1*2=2
添加到索引,否则 0*2=0
并执行 mod 4
以保持在范围内。
你的 enum
必须看起来像这样(但我猜你是自己想出来的):
enum WindingOrder {
RIGHT,
TOP,
LEFT,
BOTTOM
};
MWE:
#include <iostream>
#include <string>
#include <vector>
enum WindingOrder {
RIGHT=0,
TOP,
LEFT,
BOTTOM
};
int main()
{
std::vector<int> array = {2,4,8,9};
std::vector<int> output(4);
std::vector<WindingOrder> test = {LEFT,RIGHT,BOTTOM,TOP};
for (auto winding : test) {
for (size_t i=0; i<4; ++i) {
output[i] = array[(i+(i==winding)*2)%4];
}
std::cout << "winding " << winding << ": " << output[0] << output[1] << output[2] << output[3] << std::endl;
}
}
让我们调用我们的目标变量来索引squared
:int index
.
现在我们将为 edge
与 i
创建所需 index
的 table,edge
横跨行,i
下栏:
║0│1│2│3
═╬═╪═╪═╪═
0║0│1│2│1
─╫─┼─┼─┼─
1║2│1│2│3
─╫─┼─┼─┼─
2║2│3│0│3
─╫─┼─┼─┼─
3║0│3│0│1
由此可见,index
的最低位对于奇数i
总是奇数,对于偶数i
总是偶数。因此,如果我们能找到 index
的最高有效位,我们只需将其与 i & 1
相加,我们就会得到 index
。因此,让我们为相同的 edge
与 i
table:
制作另一个 index
的最高有效位的 table
║0│1│2│3
═╬═╪═╪═╪═
0║0│0│1│0
─╫─┼─┼─┼─
1║1│0│1│1
─╫─┼─┼─┼─
2║1│1│0│1
─╫─┼─┼─┼─
3║0│1│0│0
我们可以在这里看到几件事:
- 当
i
为 0
或 3
时,列相同仅取决于 edge
- 当
edge
为 1
或 2
时设置这些列
- 当
i
为 1
或 2
时,列彼此相反
- 只有
edge
的最高有效位或只有 i
的最高有效位被设置时才会设置这些列
所以让我们首先将 edge
和 i
分成最低有效位和最高有效位:
const int ib0 = i & 1;
const int ib1 = (i & 2) >> 1;
const int eb0 = edge & 1;
const int eb1 = (edge & 2) >> 1;
从这里我们很容易找到i
是0
还是3
:
const int iXor = ib0 ^ ib1;
对于0
/3
条件:
const int iXorCondition = ib1 ^ eb1;
并且1
/2
条件:
const int iNXorCondition = eb0 ^ eb1;
现在我们只需要将它们与它们各自的 iXor
组合起来,然后放回 index
的最低有效位:
const int index = ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0;
将所有这些放在一个方便的函数中,我们得到:
int getIndex(int i, int edge) {
const int ib0 = i & 1;
const int ib1 = (i & 2) >> 1;
const int eb0 = edge & 1;
const int eb1 = (edge & 2) >> 1;
const int iXor = ib0 ^ ib1;
const int iNXorCondition = eb0 ^ eb1;
const int iXorCondition = ib1 ^ eb1;
return ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0;
}
我写了一个检查实例 here。
是否有特殊原因需要使用大量按位运算?解决问题的方法似乎很复杂?
您似乎很担心速度,例如,您不想使用模,因为它很昂贵。既然如此,为什么不使用真正简单的查找并展开循环呢? Example on ideone as well.
编辑:感谢 chqrlie 的输入。相应地更新了答案。
#include <iostream>
using namespace std;
enum WindingOrder {
BOTTOM = 0,
RIGHT,
TOP,
LEFT
};
void DoWinding1(unsigned int const *const in, unsigned int *const out, const enum WindingOrder ord)
{
static const unsigned int order[4][4] = { [BOTTOM] = {0,1,2,1},
[RIGHT] = {2,1,2,3},
[TOP] = {2,3,0,3},
[LEFT] = {0,3,0,1} };
out[0] = in[order[ord][0]];
out[1] = in[order[ord][1]];
out[2] = in[order[ord][2]];
out[3] = in[order[ord][3]];
}
int main() {
unsigned int idx;
unsigned int rect[4] = {1, 3, 4, 5};
unsigned int out[4] = {0};
DoWinding1(rect, out, BOTTOM);
std::cout << out[0] << out[1] << out[2] << out[3] << std::endl;
return 0;
}
这是一个不同的解决方案。它是静态数组方法的一种变体,但没有实际数组:索引矩阵内联为 32 位无符号整数,计算为常量表达式。 edge
参数的列是通过一次移位选择的,最后,每个数组元素的单独索引是通过简单的位移和掩码选择的。
这个解决方案有一些优点:
- 简单易懂
- 它不使用测试
- 它不使用静态数组,也不使用任何其他内存位置
- 它独立于缠绕顺序,可以轻松定制任何阵列组件顺序
- 它不使用 C99 特定的语法,这在 C++ 中可能不可用。
这是我能得到的最接近按位解决方案。
#include <iostream>
enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT };
void BitwiseWind(int const *input, int *output, enum WindingOrder edge)
{
unsigned bits = ((0x00010201 << BOTTOM * 2) |
(0x02010203 << RIGHT * 2) |
(0x02030003 << TOP * 2) |
(0x00030001 << LEFT * 2))
>> (edge * 2);
output[0] = input[(bits >> 24) & 3];
output[1] = input[(bits >> 16) & 3];
output[2] = input[(bits >> 8) & 3];
output[3] = input[(bits >> 0) & 3];
}
int main() {
enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
int rect[4] = { 1, 3, 4, 5 };
int output[4];
for (int i = 0; i < 4; i++) {
BitwiseWind(rect, output, edges[i]);
std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
}
return 0;
}
用 clang -O3
为 x86-64
编译 BitwiseWind
生成 21 条指令,比静态数组版本多 6 条,但没有任何内存引用。这有点令人失望,但我希望它可以利用位域提取操作码为 ARM
目标生成更少的指令。顺便说一下,使用 output[i] = array[(i+(i==winding)*2)&3];
的内联版本生成了 25 条指令而没有任何跳转,而 gcc -O3
的情况更糟:它生成了更多的代码,包含 4 次测试和跳转。
下面的通用 getIndex
函数仅编译为 6 x86
条指令:
int getIndex(int i, int edge) {
return (((0x00010201 << BOTTOM * 2) |
(0x02010203 << RIGHT * 2) |
(0x02030003 << TOP * 2) |
(0x00030001 << LEFT * 2))
>> (edge * 2 + 24 - i * 8)) & 3;
}
What I want to know is can I construct the square indexes to assign to output in a for loop, without an if/case/ternary statement (in other words using bit-wise operations) ?
我想问你,你希望通过这样做达到什么目的?
我的观点是 switch-case
结构通常会被编译器的优化代码完全重组。 IMO,最好不要管那个代码,让编译器去做。
只有两种情况下我会更改该视图;
您是用 OpenCL(而不是 C)编写的,并且想要优化决策分支逻辑可能会影响性能的代码。
您想对 SIMD 向量化使用显式编码。有一些特殊的操作 可能 有帮助,但它是一个编码选项,将您锁定在没有 SIMD 指令集的硬件上可能无法正常工作的东西(或者在不同的硬件上执行完全不同) .还值得注意的是,某些编译器可以使用正确的编码进行自动矢量化。
除了 switch-case
为 C 编写这些操作之外,我只看到很少或没有任何优势。
根据您自己的回答,您已接近解决方案。我想你在这里需要的是Karnaugh map,它是大多数布尔代数问题的通用方法。
假设
The elements of the array then respectively define:
input[0]: Left edge's X coordinate
input[0]: Bottom edge's Y coordinate
input[0]: Right edge's X coordinate
input[0]: Top edge's Y coordinate
I have defined the a winding order in this enum:
enum WindingOrder {
BOTTOM = 0,
RIGHT,
TOP,
LEFT
};
因为 for 循环可能看起来像
for (int k = 0; k != 4; ++k) {
int i = getIndex(k, edge); // calculate i from k and edge
output[k] = square[i];
}
则输入为k
(output[k]
)和edge
,输出为i
(square[i]
)。又因为i
有2位,所以需要两个逻辑函数。
这里我们用P = F1(A, B, C, D)
和Q = F2(A, B, C, D)
来表示逻辑函数,其中A
、B
、C
、D
, P
和 Q
都是单位, 而
k = (A << 1) + B;
edge = (C << 1) + D;
i = (P << 1) + Q;
那么我们要做的就是根据给定的条件推导出F1
和F2
两个逻辑函数
从你给出的switch case语句中,我们可以很容易地得到真相table。
k\edge 0 1 3 2
0 0 2 0 2
1 1 1 3 3
3 1 3 1 3
2 2 2 0 0
然后把这个分成两个真值table 两个位 P
和 Q
.
P edge 0 1 3 2
k AB\CD 00 01 11 10
0 00 0 1 0 1
1 01 0 0 1 1
3 11 0 1 0 1
2 10 1 1 0 0
Q edge 0 1 3 2
k AB\CD 00 01 11 10
0 00 0 0 0 0
1 01 1 1 1 1
3 11 1 1 1 1
2 10 0 0 0 0
这些就是我开头提到的卡诺图。我们可以很容易地得到函数。
F1(A, B, C, D) = A~B~C + A~CD + ~B~CD + ~ABC + ~AC~D + BC~D
F2(A, B, C, D) = B
那么程序就是
int getIndex(int k, int edge) {
int A = (k >> 1) & 1;
int B = k & 1;
int C = (edge >> 1) & 1;
int D = edge & 1;
int P = A&~B&~C | A&~C&D | ~B&~C&D | ~A&B&C | ~A&C&~D | B&C&~D;
int Q = B;
return (P << 1) + Q;
}
通过考试here。当然,你可以用异或来进一步简化函数。
编辑
自A^B == A~B + ~AB
以来,大多数时候使用异或简化表达式是可以实现的。但这可能不是你想要的。首先,我认为 Sum of Products(SoP) 表达式和使用 XOR 的更简化版本之间的性能差异很小。其次,没有一个通用的方法(据我所知)用异或来简化一个表达式,所以你必须依靠自己的经验来完成这项工作。
两个变量有十六种可能的逻辑函数,但在数字逻辑硬件中,最简单的门电路只实现其中四种:AND、OR 以及它们的补码(NAND 和 NOR)。卡诺图用于简化现实世界的逻辑要求,以便可以使用最少数量的物理逻辑门来实现它们。
这里使用了两个常用表达式,Sum of Products 和 Product of Sums 表达式。这两个表达式可以直接使用 only AND 和 OR 逻辑运算符来实现。并且可以直接用卡诺图推导出来
这是一种实现方式:
do {
output[i] = square[
(edge & 1) * (
!(i & 1) * ((edge + 1) & 2) +
(i & 1) * (
(!((edge - 1)/2)&1) * i +
(((edge - 1)/2)&1) * (4-i)
)
) +
!(edge & 1) * (
(i & 1) * (edge + 1) +
!(i & 1) * ((edge & 2) - ((edge & 2)-1) * i)
)
];
} while(++i <= LEFT);
为了帮助您理解我缩进了代码,您显然可以删除所有空格。我在我想分开两个案例的地方放了一个标签。顺便说一句,如您所见,计算分为两个部分,用于两种不同的情况,它们是对称的,但我用不同的算法解决了每种情况,因此您可以看到实现目标的各种方法。
如果从左开始按顺时针顺序定义坐标和方向,
#define LEFT 0
#define TOP 1
#define RIGHT 2
#define BOTTOM 3
你可以使用
void edge_line(int line[4], const int rect[4], const int edge)
{
line[0] = rect[ edge & 2 ];
line[1] = rect[ ((edge + 3) & 2) + 1 ];
line[2] = rect[ ((edge + 1) & 2) ];
line[3] = rect[ (edge & 2) + 1 ];
}
复制边缘线坐标(每条线段顺时针绕线)。它看起来不是最理想的,但使用 -O2
、GCC-4.8,你基本上得到
edge_line:
pushl %esi
pushl %ebx
movl 20(%esp), %ecx
movl 16(%esp), %edx
movl 12(%esp), %eax
movl %ecx, %esi
andl , %esi
movl (%edx,%esi,4), %ebx
movl %ebx, (%eax)
leal 3(%ecx), %ebx
addl , %ecx
andl , %ebx
andl , %ecx
addl , %ebx
movl (%edx,%ebx,4), %ebx
movl %ebx, 4(%eax)
movl (%edx,%ecx,4), %ecx
movl %ecx, 8(%eax)
movl 4(%edx,%esi,4), %edx
movl %edx, 12(%eax)
popl %ebx
popl %esi
ret
但在 64 位上,甚至更好
edge_line:
movl %edx, %ecx
andl , %ecx
movslq %ecx, %rcx
movl (%rsi,%rcx,4), %eax
movl %eax, (%rdi)
leal 3(%rdx), %eax
addl , %edx
andl , %edx
andl , %eax
movslq %edx, %rdx
cltq
movl 4(%rsi,%rax,4), %eax
movl %eax, 4(%rdi)
movl (%rsi,%rdx,4), %eax
movl %eax, 8(%rdi)
movl 4(%rsi,%rcx,4), %eax
movl %eax, 12(%rdi)
ret
如您所见,没有条件语句,二元运算符组合并优化了很少的指令。
编辑添加:
如果我们定义一个getIndex(i, edge)
函数,使用三个二进制与、一个位移位(右移1)、三个加法和一个减法,
int getIndex(const int i, const int edge)
{
return (i & 1) + ((edge + 4 - (i & 1) + (i >> 1)) & 2);
}
其中 edge_line()
可以实现为
void edge_line(int line[4], const int rect[4], const int edge)
{
line[0] = rect[ getIndex(0, edge) ];
line[1] = rect[ getIndex(1, edge) ];
line[2] = rect[ getIndex(2, edge) ];
line[3] = rect[ getIndex(3, edge) ];
}
我们得到与以前完全相同的结果。在 AMD64/x86-64 上使用 GCC-4.8.4 和 -O2
编译为
getIndex:
movl %edi, %edx
sarl %edi
andl , %edx
subl %edx, %esi
leal 4(%rsi,%rdi), %eax
andl , %eax
addl %edx, %eax
ret
然后到
getIndex:
movl 4(%esp), %eax
movl 8(%esp), %edx
movl %eax, %ecx
andl , %ecx
subl %ecx, %edx
sarl %eax
leal 4(%edx,%eax), %eax
andl , %eax
addl %ecx, %eax
ret
在 i686 上。请注意,我使用四乘四的结果 table 得到了上面的表格;还有其他更严格的方法来构造它,甚至可能有更优化的形式。因此,我强烈建议在函数上方添加一个巨大的注释,解释意图,最好也显示结果 table。像
/* This function returns an array index:
* 0 for left
* 1 for top
* 2 for right
* 3 for bottom
* given edge:
* 0 for left
* 1 for top
* 2 for right
* 3 for bottom
* and i:
* 0 for initial x
* 1 for initial y
* 2 for final x
* 3 for final y
*
* The result table is
* | edge
* | 0 1 2 3
* ----+-------
* i=0 | 0 0 2 2
* i=1 | 3 1 1 3
* i=2 | 0 2 2 0
* i=3 | 1 1 3 3
*
* Apologies for the write-only code.
*/
或类似的东西。
是否可以重新定义 WindingOrder 的值集?如果可能的话,这是我的解决方案,它尝试在 WindingOrder 的值集中编码 selection 索引,然后通过移位和屏蔽只要 [=13] 简单地解码出 input[]
的 select 索引=] 索引迭代。
[感谢 chqrlie 提供代码库]:
#include <iostream>
enum WindingOrder {
// the RIGHT most 4-bits indicate the selection index from input[] to output[0]
// the LEFT most 4-bits indicate the selection index from input[] to output[3]
BOTTOM = 0x1210,
RIGHT = 0x3212,
TOP = 0x3230,
LEFT = 0x3010
};
void BitwiseWind(int const *input, int *output, unsigned short edge)
{
for (size_t i = 0; i < 4; i++)
output[i] = input[(edge >> (i*4)) & 0x000F]; // decode
}
int main() {
enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
int rect[4] = { 1, 3, 4, 5 };
int output[4];
for (int i = 0; i < 4; i++) {
BitwiseWind(rect, output, edges[i]);
std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
}
return 0;
}
通用的 getIndex(int i,enum WindingOrder edge) 将是:
int getIndex(int i,enum WindingOrder edge)
{
return ((edge >> (i*4)) & 0x000F);
}
我没数过它使用了多少条指令,但我相信它会很少。而且真的很容易想象它是如何工作的。 :)
我有 2 个 2D 点,它们挤在一起形成一个数组:int square[4]
。这四个数字被解释为具有平行于 X 轴的水平线和平行于 Y 轴的垂直线的矩形的定义。然后数组的元素分别定义:
- 左边的X坐标
- 底边的Y坐标
- 右边缘的X坐标
- 顶边的Y坐标
我已经在这个enum
中定义了绕组顺序:
enum WindingOrder {
BOTTOM = 0,
RIGHT,
TOP,
LEFT
};
我的代码的最小、完整、可验证的示例是,我得到了一个输出第二数组:int output[4]
和一个输入 WindingOrder edge
。我需要按如下方式填充 output
:
switch(edge) {
case BOTTOM:
output[0] = square[0]; output[1] = square[1]; output[2] = square[2]; output[3] = square[1];
break;
case RIGHT:
output[0] = square[2]; output[1] = square[1]; output[2] = square[2]; output[3] = square[3];
break;
case TOP:
output[0] = square[2]; output[1] = square[3]; output[2] = square[0]; output[3] = square[3];
break;
case LEFT:
output[0] = square[0]; output[1] = square[3]; output[2] = square[0]; output[3] = square[1];
break;
}
我没有嫁给特定的 WindingOrder
安排,我也不关心 ouptut
中的点的顺序,所以如果改变这些可以解决这个问题,我会失望的。我想知道的是我可以在 for
循环中构造 square
索引以分配给 output
, 没有 和 if
/case
/三元语句(换句话说使用按位运算)?
所以我想,给定 int i = 0
和 WindingOrder edge
对它们进行按位运算以找到:
do {
output[i] = array[???];
} while(++i <= LEFT);
编辑:
我收到了很多静态数组的答案(我认为这是解决这个问题的最佳方法,所以我给了 +1)。但作为一个逻辑问题,我很好奇可以采用多少位运算来动态查找给定边的元素。因此,例如,在给定任意 edge
和 i
的情况下,该函数的主体应该如何编写:int getIndex(int i, int edge)
这是未经测试的,在某些细节上可能存在小错误,但总体思路应该可行。
将数组复制到输出将使用索引 {0,1,2,3}
。要获得特定优势,您必须对索引进行一些转换:
changed_pos changed_to
RIGHT : {2,1,2,3} 0 2
TOP : {0,3,2,3} 1 3
LEFT : {0,1,0,3} 2 0
BOTTOM: {0,1,2,1} 3 1
所以基本上你必须为你的绕组的具体位置添加2 mod 4
。
所以(就像我说的未经测试的)剪断可能看起来像这样
for (size_t i=0; i<4; ++i) {
output[i] = array[(i+(i==edge)*2)%4];
}
如果比较结果为真,则将 1*2=2
添加到索引,否则 0*2=0
并执行 mod 4
以保持在范围内。
你的 enum
必须看起来像这样(但我猜你是自己想出来的):
enum WindingOrder {
RIGHT,
TOP,
LEFT,
BOTTOM
};
MWE:
#include <iostream>
#include <string>
#include <vector>
enum WindingOrder {
RIGHT=0,
TOP,
LEFT,
BOTTOM
};
int main()
{
std::vector<int> array = {2,4,8,9};
std::vector<int> output(4);
std::vector<WindingOrder> test = {LEFT,RIGHT,BOTTOM,TOP};
for (auto winding : test) {
for (size_t i=0; i<4; ++i) {
output[i] = array[(i+(i==winding)*2)%4];
}
std::cout << "winding " << winding << ": " << output[0] << output[1] << output[2] << output[3] << std::endl;
}
}
让我们调用我们的目标变量来索引squared
:int index
.
现在我们将为 edge
与 i
创建所需 index
的 table,edge
横跨行,i
下栏:
║0│1│2│3
═╬═╪═╪═╪═
0║0│1│2│1
─╫─┼─┼─┼─
1║2│1│2│3
─╫─┼─┼─┼─
2║2│3│0│3
─╫─┼─┼─┼─
3║0│3│0│1
由此可见,index
的最低位对于奇数i
总是奇数,对于偶数i
总是偶数。因此,如果我们能找到 index
的最高有效位,我们只需将其与 i & 1
相加,我们就会得到 index
。因此,让我们为相同的 edge
与 i
table:
index
的最高有效位的 table
║0│1│2│3
═╬═╪═╪═╪═
0║0│0│1│0
─╫─┼─┼─┼─
1║1│0│1│1
─╫─┼─┼─┼─
2║1│1│0│1
─╫─┼─┼─┼─
3║0│1│0│0
我们可以在这里看到几件事:
- 当
i
为0
或3
时,列相同仅取决于edge
- 当
edge
为1
或2
时设置这些列
- 当
- 当
i
为1
或2
时,列彼此相反- 只有
edge
的最高有效位或只有i
的最高有效位被设置时才会设置这些列
- 只有
所以让我们首先将 edge
和 i
分成最低有效位和最高有效位:
const int ib0 = i & 1;
const int ib1 = (i & 2) >> 1;
const int eb0 = edge & 1;
const int eb1 = (edge & 2) >> 1;
从这里我们很容易找到i
是0
还是3
:
const int iXor = ib0 ^ ib1;
对于0
/3
条件:
const int iXorCondition = ib1 ^ eb1;
并且1
/2
条件:
const int iNXorCondition = eb0 ^ eb1;
现在我们只需要将它们与它们各自的 iXor
组合起来,然后放回 index
的最低有效位:
const int index = ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0;
将所有这些放在一个方便的函数中,我们得到:
int getIndex(int i, int edge) {
const int ib0 = i & 1;
const int ib1 = (i & 2) >> 1;
const int eb0 = edge & 1;
const int eb1 = (edge & 2) >> 1;
const int iXor = ib0 ^ ib1;
const int iNXorCondition = eb0 ^ eb1;
const int iXorCondition = ib1 ^ eb1;
return ((iNXorCondition & ~iXor | iXorCondition & iXor) << 1) | ib0;
}
我写了一个检查实例 here。
是否有特殊原因需要使用大量按位运算?解决问题的方法似乎很复杂?
您似乎很担心速度,例如,您不想使用模,因为它很昂贵。既然如此,为什么不使用真正简单的查找并展开循环呢? Example on ideone as well.
编辑:感谢 chqrlie 的输入。相应地更新了答案。
#include <iostream>
using namespace std;
enum WindingOrder {
BOTTOM = 0,
RIGHT,
TOP,
LEFT
};
void DoWinding1(unsigned int const *const in, unsigned int *const out, const enum WindingOrder ord)
{
static const unsigned int order[4][4] = { [BOTTOM] = {0,1,2,1},
[RIGHT] = {2,1,2,3},
[TOP] = {2,3,0,3},
[LEFT] = {0,3,0,1} };
out[0] = in[order[ord][0]];
out[1] = in[order[ord][1]];
out[2] = in[order[ord][2]];
out[3] = in[order[ord][3]];
}
int main() {
unsigned int idx;
unsigned int rect[4] = {1, 3, 4, 5};
unsigned int out[4] = {0};
DoWinding1(rect, out, BOTTOM);
std::cout << out[0] << out[1] << out[2] << out[3] << std::endl;
return 0;
}
这是一个不同的解决方案。它是静态数组方法的一种变体,但没有实际数组:索引矩阵内联为 32 位无符号整数,计算为常量表达式。 edge
参数的列是通过一次移位选择的,最后,每个数组元素的单独索引是通过简单的位移和掩码选择的。
这个解决方案有一些优点:
- 简单易懂
- 它不使用测试
- 它不使用静态数组,也不使用任何其他内存位置
- 它独立于缠绕顺序,可以轻松定制任何阵列组件顺序
- 它不使用 C99 特定的语法,这在 C++ 中可能不可用。
这是我能得到的最接近按位解决方案。
#include <iostream>
enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT };
void BitwiseWind(int const *input, int *output, enum WindingOrder edge)
{
unsigned bits = ((0x00010201 << BOTTOM * 2) |
(0x02010203 << RIGHT * 2) |
(0x02030003 << TOP * 2) |
(0x00030001 << LEFT * 2))
>> (edge * 2);
output[0] = input[(bits >> 24) & 3];
output[1] = input[(bits >> 16) & 3];
output[2] = input[(bits >> 8) & 3];
output[3] = input[(bits >> 0) & 3];
}
int main() {
enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
int rect[4] = { 1, 3, 4, 5 };
int output[4];
for (int i = 0; i < 4; i++) {
BitwiseWind(rect, output, edges[i]);
std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
}
return 0;
}
用 clang -O3
为 x86-64
编译 BitwiseWind
生成 21 条指令,比静态数组版本多 6 条,但没有任何内存引用。这有点令人失望,但我希望它可以利用位域提取操作码为 ARM
目标生成更少的指令。顺便说一下,使用 output[i] = array[(i+(i==winding)*2)&3];
的内联版本生成了 25 条指令而没有任何跳转,而 gcc -O3
的情况更糟:它生成了更多的代码,包含 4 次测试和跳转。
下面的通用 getIndex
函数仅编译为 6 x86
条指令:
int getIndex(int i, int edge) {
return (((0x00010201 << BOTTOM * 2) |
(0x02010203 << RIGHT * 2) |
(0x02030003 << TOP * 2) |
(0x00030001 << LEFT * 2))
>> (edge * 2 + 24 - i * 8)) & 3;
}
What I want to know is can I construct the square indexes to assign to output in a for loop, without an if/case/ternary statement (in other words using bit-wise operations) ?
我想问你,你希望通过这样做达到什么目的?
我的观点是 switch-case
结构通常会被编译器的优化代码完全重组。 IMO,最好不要管那个代码,让编译器去做。
只有两种情况下我会更改该视图;
您是用 OpenCL(而不是 C)编写的,并且想要优化决策分支逻辑可能会影响性能的代码。
您想对 SIMD 向量化使用显式编码。有一些特殊的操作 可能 有帮助,但它是一个编码选项,将您锁定在没有 SIMD 指令集的硬件上可能无法正常工作的东西(或者在不同的硬件上执行完全不同) .还值得注意的是,某些编译器可以使用正确的编码进行自动矢量化。
除了 switch-case
为 C 编写这些操作之外,我只看到很少或没有任何优势。
根据您自己的回答,您已接近解决方案。我想你在这里需要的是Karnaugh map,它是大多数布尔代数问题的通用方法。
假设
The elements of the array then respectively define:
input[0]: Left edge's X coordinate input[0]: Bottom edge's Y coordinate input[0]: Right edge's X coordinate input[0]: Top edge's Y coordinate
I have defined the a winding order in this enum:
enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT };
因为 for 循环可能看起来像
for (int k = 0; k != 4; ++k) {
int i = getIndex(k, edge); // calculate i from k and edge
output[k] = square[i];
}
则输入为k
(output[k]
)和edge
,输出为i
(square[i]
)。又因为i
有2位,所以需要两个逻辑函数。
这里我们用P = F1(A, B, C, D)
和Q = F2(A, B, C, D)
来表示逻辑函数,其中A
、B
、C
、D
, P
和 Q
都是单位, 而
k = (A << 1) + B;
edge = (C << 1) + D;
i = (P << 1) + Q;
那么我们要做的就是根据给定的条件推导出F1
和F2
两个逻辑函数
从你给出的switch case语句中,我们可以很容易地得到真相table。
k\edge 0 1 3 2
0 0 2 0 2
1 1 1 3 3
3 1 3 1 3
2 2 2 0 0
然后把这个分成两个真值table 两个位 P
和 Q
.
P edge 0 1 3 2
k AB\CD 00 01 11 10
0 00 0 1 0 1
1 01 0 0 1 1
3 11 0 1 0 1
2 10 1 1 0 0
Q edge 0 1 3 2
k AB\CD 00 01 11 10
0 00 0 0 0 0
1 01 1 1 1 1
3 11 1 1 1 1
2 10 0 0 0 0
这些就是我开头提到的卡诺图。我们可以很容易地得到函数。
F1(A, B, C, D) = A~B~C + A~CD + ~B~CD + ~ABC + ~AC~D + BC~D
F2(A, B, C, D) = B
那么程序就是
int getIndex(int k, int edge) {
int A = (k >> 1) & 1;
int B = k & 1;
int C = (edge >> 1) & 1;
int D = edge & 1;
int P = A&~B&~C | A&~C&D | ~B&~C&D | ~A&B&C | ~A&C&~D | B&C&~D;
int Q = B;
return (P << 1) + Q;
}
通过考试here。当然,你可以用异或来进一步简化函数。
编辑
自A^B == A~B + ~AB
以来,大多数时候使用异或简化表达式是可以实现的。但这可能不是你想要的。首先,我认为 Sum of Products(SoP) 表达式和使用 XOR 的更简化版本之间的性能差异很小。其次,没有一个通用的方法(据我所知)用异或来简化一个表达式,所以你必须依靠自己的经验来完成这项工作。
两个变量有十六种可能的逻辑函数,但在数字逻辑硬件中,最简单的门电路只实现其中四种:AND、OR 以及它们的补码(NAND 和 NOR)。卡诺图用于简化现实世界的逻辑要求,以便可以使用最少数量的物理逻辑门来实现它们。
这里使用了两个常用表达式,Sum of Products 和 Product of Sums 表达式。这两个表达式可以直接使用 only AND 和 OR 逻辑运算符来实现。并且可以直接用卡诺图推导出来
这是一种实现方式:
do {
output[i] = square[
(edge & 1) * (
!(i & 1) * ((edge + 1) & 2) +
(i & 1) * (
(!((edge - 1)/2)&1) * i +
(((edge - 1)/2)&1) * (4-i)
)
) +
!(edge & 1) * (
(i & 1) * (edge + 1) +
!(i & 1) * ((edge & 2) - ((edge & 2)-1) * i)
)
];
} while(++i <= LEFT);
为了帮助您理解我缩进了代码,您显然可以删除所有空格。我在我想分开两个案例的地方放了一个标签。顺便说一句,如您所见,计算分为两个部分,用于两种不同的情况,它们是对称的,但我用不同的算法解决了每种情况,因此您可以看到实现目标的各种方法。
如果从左开始按顺时针顺序定义坐标和方向,
#define LEFT 0
#define TOP 1
#define RIGHT 2
#define BOTTOM 3
你可以使用
void edge_line(int line[4], const int rect[4], const int edge)
{
line[0] = rect[ edge & 2 ];
line[1] = rect[ ((edge + 3) & 2) + 1 ];
line[2] = rect[ ((edge + 1) & 2) ];
line[3] = rect[ (edge & 2) + 1 ];
}
复制边缘线坐标(每条线段顺时针绕线)。它看起来不是最理想的,但使用 -O2
、GCC-4.8,你基本上得到
edge_line:
pushl %esi
pushl %ebx
movl 20(%esp), %ecx
movl 16(%esp), %edx
movl 12(%esp), %eax
movl %ecx, %esi
andl , %esi
movl (%edx,%esi,4), %ebx
movl %ebx, (%eax)
leal 3(%ecx), %ebx
addl , %ecx
andl , %ebx
andl , %ecx
addl , %ebx
movl (%edx,%ebx,4), %ebx
movl %ebx, 4(%eax)
movl (%edx,%ecx,4), %ecx
movl %ecx, 8(%eax)
movl 4(%edx,%esi,4), %edx
movl %edx, 12(%eax)
popl %ebx
popl %esi
ret
但在 64 位上,甚至更好
edge_line:
movl %edx, %ecx
andl , %ecx
movslq %ecx, %rcx
movl (%rsi,%rcx,4), %eax
movl %eax, (%rdi)
leal 3(%rdx), %eax
addl , %edx
andl , %edx
andl , %eax
movslq %edx, %rdx
cltq
movl 4(%rsi,%rax,4), %eax
movl %eax, 4(%rdi)
movl (%rsi,%rdx,4), %eax
movl %eax, 8(%rdi)
movl 4(%rsi,%rcx,4), %eax
movl %eax, 12(%rdi)
ret
如您所见,没有条件语句,二元运算符组合并优化了很少的指令。
编辑添加:
如果我们定义一个getIndex(i, edge)
函数,使用三个二进制与、一个位移位(右移1)、三个加法和一个减法,
int getIndex(const int i, const int edge)
{
return (i & 1) + ((edge + 4 - (i & 1) + (i >> 1)) & 2);
}
其中 edge_line()
可以实现为
void edge_line(int line[4], const int rect[4], const int edge)
{
line[0] = rect[ getIndex(0, edge) ];
line[1] = rect[ getIndex(1, edge) ];
line[2] = rect[ getIndex(2, edge) ];
line[3] = rect[ getIndex(3, edge) ];
}
我们得到与以前完全相同的结果。在 AMD64/x86-64 上使用 GCC-4.8.4 和 -O2
编译为
getIndex:
movl %edi, %edx
sarl %edi
andl , %edx
subl %edx, %esi
leal 4(%rsi,%rdi), %eax
andl , %eax
addl %edx, %eax
ret
然后到
getIndex:
movl 4(%esp), %eax
movl 8(%esp), %edx
movl %eax, %ecx
andl , %ecx
subl %ecx, %edx
sarl %eax
leal 4(%edx,%eax), %eax
andl , %eax
addl %ecx, %eax
ret
在 i686 上。请注意,我使用四乘四的结果 table 得到了上面的表格;还有其他更严格的方法来构造它,甚至可能有更优化的形式。因此,我强烈建议在函数上方添加一个巨大的注释,解释意图,最好也显示结果 table。像
/* This function returns an array index:
* 0 for left
* 1 for top
* 2 for right
* 3 for bottom
* given edge:
* 0 for left
* 1 for top
* 2 for right
* 3 for bottom
* and i:
* 0 for initial x
* 1 for initial y
* 2 for final x
* 3 for final y
*
* The result table is
* | edge
* | 0 1 2 3
* ----+-------
* i=0 | 0 0 2 2
* i=1 | 3 1 1 3
* i=2 | 0 2 2 0
* i=3 | 1 1 3 3
*
* Apologies for the write-only code.
*/
或类似的东西。
是否可以重新定义 WindingOrder 的值集?如果可能的话,这是我的解决方案,它尝试在 WindingOrder 的值集中编码 selection 索引,然后通过移位和屏蔽只要 [=13] 简单地解码出 input[]
的 select 索引=] 索引迭代。
[感谢 chqrlie 提供代码库]:
#include <iostream>
enum WindingOrder {
// the RIGHT most 4-bits indicate the selection index from input[] to output[0]
// the LEFT most 4-bits indicate the selection index from input[] to output[3]
BOTTOM = 0x1210,
RIGHT = 0x3212,
TOP = 0x3230,
LEFT = 0x3010
};
void BitwiseWind(int const *input, int *output, unsigned short edge)
{
for (size_t i = 0; i < 4; i++)
output[i] = input[(edge >> (i*4)) & 0x000F]; // decode
}
int main() {
enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
int rect[4] = { 1, 3, 4, 5 };
int output[4];
for (int i = 0; i < 4; i++) {
BitwiseWind(rect, output, edges[i]);
std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
}
return 0;
}
通用的 getIndex(int i,enum WindingOrder edge) 将是:
int getIndex(int i,enum WindingOrder edge)
{
return ((edge >> (i*4)) & 0x000F);
}
我没数过它使用了多少条指令,但我相信它会很少。而且真的很容易想象它是如何工作的。 :)