我有一些无符号的16位整数，我想映射到一个无符号的32位整数，s中的每个翻转位在r中最多翻转一个（给定的）位，这只是s和r之间的映射。所以我们可以把它看作一个矩阵方程
Ps = r
其中P是布尔矩阵，
0..16是布尔向量，0..32是布尔向量。我有一种直觉，我错过了一些简单的黑客。重要提示：目标机器是16位mcu！我只能这样做：
static u16 P[32] = someArrayOrWhatever();
u32 FsiPermutationHack(u16 s) {
u32 r;
for (u16 i = 0; i < 32; i++)
{
r |= ((u32)((P[i] & s) > 0) << i);
}
return r;
}
其基本原理是：第i:th位
32 x 16是1 if且仅当s时。我太蠢了，不想把东西拆开，但我猜如果我们不需要做那个愚蠢的16 x 1演员的话，这会是大约100个指令。不过，也许编译器会自动将循环分成两部分，在这种情况下，它看起来非常适合我们。为切点道歉，我只是想和你分享我尝试过的解决方法——你有更好的方法吗？
最佳答案
正如你所说，
我猜如果我们没有
做那个愚蠢的u32演员。但话说回来，也许编译器
自动将循环一分为二，这样看起来很漂亮
对我们有好处。
和
我有一种直觉，我错过了一些超简单的黑客。
，我将把您理解为询问如何在这段代码中最小化32位算术的使用，这段代码是针对16位处理器的。
你真的应该学习如何反汇编并检查编译的结果，看看编译器是否像你所假设的那样自动拆分循环，但是假设它没有，我不明白你为什么不能手动执行同样的操作：
static u16 P[32]; /* value assigned elsewhere */
u32 FsiPermutationHack(u16 s) {
u16 *P_hi = P + 16;
u16 r_lo = 0;
u16 r_hi = 0;
for (u16 i = 0; i < 16; i++) {
r_lo |= (P[i] & s) != 0) << i;
r_hi |= (P_hi[i] & s) != 0) << i;
}
return ((u32) r_hi << 16) + r_lo;
}
假设
u16和u32分别是无符号的16位和32位整数，没有填充位。还需要注意的是，执行
u16类型而不是u32类型的算术应该是一种改进，假设u32类型具有比unsigned int更高的整数提升秩。粗略地说，这归结为实现的unsigned int是16位类型。对于16位处理器的实现来说，这是完全合理的。但是，在int和unsigned int都是32位类型的系统上，所有较窄的整数算术参数都将提升为32位。更新：
至于更好的替代算法的可能性，我观察到，结果的每一位都是从数组的不同元素
P中计算出来的，使用了每个元素的整个值，并且元素大小与目标机器的本机字大小相同。因此，似乎没有比数组元素执行更少的16位逐位和操作的范围（但请参见下文）。如果我们接受每个数组元素都必须单独处理，那么提供的实现在高效处理它方面做得相当好：
它只执行16位计算，直到时间到了汇编最终结果；
它在同一个循环中计算结果的上半部分和下半部分，因此只产生16次迭代的循环开销，而不是32次
它很大程度上去除了创建索引
P_hi以访问数组的上半部分所需的额外索引算法。手动展开循环可能会节省更多的周期，但这是一种您绝对应该依赖编译器为您执行的优化。
就“比特旋转黑客”而言，我看到的唯一一个这种性质的范围是将相邻的16位数组元素对作为32位无符号整数进行处理。这将允许执行一个32位的位，并代替每两个16位的ANDs。这将与两个32位比较（与上述代码中的两个16位比较）相结合。可以保留上述方法的16位移位和按位或操作。除了由于违反严格的别名规则而导致的形式上未定义的行为外，这将涉及32位算法，这大概是16位计算机上16位算法的一半速度。业绩的衡量要比预期的好，但我看不出有任何理由期待这种方法能取得重大胜利。