优化：删除分支
Optimization: removing branch
我懂一点 C。我尝试编写一个程序，它不使用条件语句，而是对给定的整数数组添加奇数和乘以偶数。 if odd add n else add 0 部分并不难写。但是，我无法计算出乘法部分。解决方案似乎是 如果奇数则乘以 1，否则乘以 n。
所以，我的问题是 给定一个整数，如果它是给定整数的奇数，如何将其转换为 1。不允许有条件。或者，如果可能的话，一个更好的主意。提前致谢。
所以让我无耻地撕掉@SeverinPappadeux 的评论并稍微修改一下，这样我就可以声称它是我自己的了：
res = i % 2 + (1 - i % 2) * number;
^^^^^ ^^^^^^^^^
odd: 1 0
even: 0 1
好了：
int Get1IfOddValOtherwise(int val)
{
return (1-(val&1))*(val-1)+1;
}
您可以轻松检查最后一点。这样，你就知道这个数字是奇数还是偶数。
last_bit = number & 0x01;
first_number = last_bit;
如果最后一位为零，则第一个数字为零。如果不是（奇数），则为 1.
然后你取 last_bit 并反转最后一位
last_bit = (last_bit+1) & 0x01;
second_number = last_bit * n;
现在 second_number 是 n 或 0。
result = (first_number + second_number);
好的，要求提供答案。表达式
res = (i % 2) + ((i+1) % 2) * number;
如果 i 是奇数， 将 return 1，否则给出 number
res = (i % 2) ? 1: number;
条件执行，或者分支预测是最好的选择。
现在的小树枝没那么邪恶了
编辑
是分支预测ation，不是分支预测。
没有乘法，假设 2s 补码运算（如果不是，则将 i 转换为无符号）：
/* implements odd(i) ? 1 : n */
(((i&1)-1)&(n-1)) + 1
- i&1 如果 i 是奇数则为 1，否则为 0，所以
- (i&1)-1 如果 i 是奇数则为 0，否则为 -1。
- 由于 -1 的 2s 补码表示将所有位设置为 1：
- ((i&1)-1)&(n-1) 如果 i 是奇数则为 0，否则为 (n-1)，所以
- (((i&1)-1)&(n-1))+1 如果 i 为奇数则为 1，否则为 n。
这是否比乘法快在很大程度上取决于体系结构；在现代 CPU 上，这是值得怀疑的，但在嵌入式架构上，它是值得怀疑的。它肯定不比编译器生成的条件移动快，而且很难阅读。还是...
这是另一个无乘法的版本（也采用二进制补码）。逻辑是 & 偶数为 11...11 (-1) 的数字（11...1x，其中 x 是 don 't care 也可以工作......也许可以以某种方式使用）并且 00...01 用于奇数。然后问题归结为将奇数和偶数转换为这些掩码。
n&(((n&1) << 1) - 1)
(n&1) << 1偶数为0，奇数为2。减一得到所需的掩码。
（如前所述，您通常最好还是执行 n % 2 ? n : 1 而不是尝试事后猜测优化器。如果编译器认为值得，它可能会为此生成无分支条件移动。）
在其他答案中已经指出，奇数和偶数的指标是i%2和(i+1)%2。
您可以用它来解决一行中的全部问题：
result = (i%2)*(number+i)+((i+1)%2)*number*i
你必须注意 i 永远不会是负面的。如果仍然可行，那么您可以通过双重 mod 操作使情况正常化：(2+i%2)%2 和 (2+(i+1)%2)%2.
当然，使用分支可以使它更短，如
result = (i%2)?(i+number):(i*number)
我懂一点 C。我尝试编写一个程序，它不使用条件语句，而是对给定的整数数组添加奇数和乘以偶数。 if odd add n else add 0 部分并不难写。但是，我无法计算出乘法部分。解决方案似乎是 如果奇数则乘以 1，否则乘以 n。
所以，我的问题是 给定一个整数，如果它是给定整数的奇数，如何将其转换为 1。不允许有条件。或者，如果可能的话，一个更好的主意。提前致谢。
所以让我无耻地撕掉@SeverinPappadeux 的评论并稍微修改一下，这样我就可以声称它是我自己的了：
res = i % 2 + (1 - i % 2) * number;
^^^^^ ^^^^^^^^^
odd: 1 0
even: 0 1
好了：
int Get1IfOddValOtherwise(int val)
{
return (1-(val&1))*(val-1)+1;
}
您可以轻松检查最后一点。这样，你就知道这个数字是奇数还是偶数。
last_bit = number & 0x01;
first_number = last_bit;
如果最后一位为零，则第一个数字为零。如果不是（奇数），则为 1.
然后你取 last_bit 并反转最后一位
last_bit = (last_bit+1) & 0x01;
second_number = last_bit * n;
现在 second_number 是 n 或 0。
result = (first_number + second_number);
好的，要求提供答案。表达式
res = (i % 2) + ((i+1) % 2) * number;
i 是奇数， 将 return 1，否则给出 number
res = (i % 2) ? 1: number;
条件执行，或者分支预测是最好的选择。
现在的小树枝没那么邪恶了
编辑 是分支预测ation，不是分支预测。
没有乘法，假设 2s 补码运算（如果不是，则将 i 转换为无符号）：
/* implements odd(i) ? 1 : n */
(((i&1)-1)&(n-1)) + 1
- i&1 如果 i 是奇数则为 1，否则为 0，所以
- (i&1)-1 如果 i 是奇数则为 0，否则为 -1。
- 由于 -1 的 2s 补码表示将所有位设置为 1：
- ((i&1)-1)&(n-1) 如果 i 是奇数则为 0，否则为 (n-1)，所以
- (((i&1)-1)&(n-1))+1 如果 i 为奇数则为 1，否则为 n。
这是否比乘法快在很大程度上取决于体系结构；在现代 CPU 上，这是值得怀疑的，但在嵌入式架构上，它是值得怀疑的。它肯定不比编译器生成的条件移动快，而且很难阅读。还是...
这是另一个无乘法的版本（也采用二进制补码）。逻辑是 & 偶数为 11...11 (-1) 的数字（11...1x，其中 x 是 don 't care 也可以工作......也许可以以某种方式使用）并且 00...01 用于奇数。然后问题归结为将奇数和偶数转换为这些掩码。
n&(((n&1) << 1) - 1)
(n&1) << 1偶数为0，奇数为2。减一得到所需的掩码。
（如前所述，您通常最好还是执行 n % 2 ? n : 1 而不是尝试事后猜测优化器。如果编译器认为值得，它可能会为此生成无分支条件移动。）
在其他答案中已经指出，奇数和偶数的指标是i%2和(i+1)%2。
您可以用它来解决一行中的全部问题：
result = (i%2)*(number+i)+((i+1)%2)*number*i
你必须注意 i 永远不会是负面的。如果仍然可行，那么您可以通过双重 mod 操作使情况正常化：(2+i%2)%2 和 (2+(i+1)%2)%2.
当然，使用分支可以使它更短，如
result = (i%2)?(i+number):(i*number)