Tim*_*Tim 40 c++ math unsigned-integer
单独使用整数数学,我想在C++中"安全地"平均两个无符号整数.
我所说的"安全"是避免溢出(以及任何其他可以想到的).
例如,平均200和5000很容易:
unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended
但是在4294967295和5000的情况下:
unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147
我提出的最好的是:
unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected
还有更好的方法吗？
sel*_*tze 52
你最后的方法似乎很有希望 您可以通过手动考虑a和b的最低位来改进:
unsigned int average = (a / 2) + (b / 2) + (a & b & 1);
如果a和b都是奇数,则给出正确的结果.
She*_*per 27
unsigned int average = low + ((high - low) / 2);
编辑
这是一篇相关文章:http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
ini*_*iju 17
如果两个数字都是奇数,例如5和7,平均值为6,但是方法#3返回5,则表示方法不正确.
试试这个:
average = (a>>1) + (b>>1) + (a & b & 1)
仅限数学运算符:
average = a/2 + b/2 + (a%2) * (b%2)
如果你不介意一点x86内联汇编(GNU C语法),你可以利用supercat的建议在add之后使用rotate-with-carry将完整的33位结果的高32位放入寄存器.
当然,您通常应该介意使用inline-asm,因为它会破坏一些优化(https://gcc.gnu.org/wiki/DontUseInlineAsm).但无论如何我们走了:
// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
unsigned result;
asm("add %[x], %[res]\n\t"
"rcr %[res]"
: [res] "=r" (result) // output
: [y] "%0"(y), // input: in the same reg as results output. Commutative with next operand
[x] "rme"(x) // input: reg, mem, or immediate
: // no clobbers. ("cc" is implicit on x86)
);
return result;
}
告诉编译器args是可交换的%修饰符实际上并没有帮助在我尝试的情况下做出更好的asm,调用y是常量或指针deref(内存操作数)的函数.可能对输出操作数使用匹配约束会使其失败,因为您无法将其与读写操作数一起使用.
正如您在Godbolt编译器浏览器中看到的那样,这可以正确编译,我们将操作数更改为unsigned long具有相同内联asm 的版本也是如此.然而clang3.9弄得一团糟,并决定使用约束"m"选项"rme",因此它存储到内存并使用内存操作数.
RCR-by-one并不是太慢,但Skylake上还有3个uop,有2个周期延迟.它在AMD CPU上非常出色,其中RCR具有单周期延迟.(来源:Agner Fog的指令表,另见x86标签wiki for x86性能链接).它仍然比@ sellibitze的版本更好,但比@ Sheldon的依赖订单的版本更糟糕.(参见Godbolt的代码)
但请记住,inline-asm会破坏常量传播等优化,因此在这种情况下,任何纯C++版本都会更好.
你所拥有的很好，有一个小细节，它会声称 3 和 3 的平均值是 2。我猜你不希望这样；幸运的是，有一个简单的解决方法：
unsigned int average = a/2 + b/2 + (a & b & 1);
在两个部门都被截断的情况下，这只会使平均数回升。