我怎么可以安全地平均两unsigned int在C++？

StackOverflow https://stackoverflow.com/questions/3816446

  •  26-09-2019
  •  | 
  •  

题

使用的整数单独，我想到"安全的"平均两unsigned int在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

是否有更好的方法?

有帮助吗？

解决方案

你最后一次的办法似乎有前途的。你可以改进的，通过手动考虑到最低位的a和b：

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

这给正确的结果在情况a和b两者都是奇数。

其他提示

unsigned int average = low + ((high - low) / 2);

编辑

这里有一个相关的文章： http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

你的方法是不正确的，如果两个数字都怪例如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 syntax)，可以利用的supercat的建议使用 旋转与携带 之后添加把高的32位的全33位导致进入一个登记册。

当然，你通常 应该 介意使用内联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编译器explorer, 这正确编译，所以没有一个版本在哪里我们改变的操作数 unsigned long, ，有相同的内联asm。clang3.9弄得一团糟，不过，并决定使用 "m" 选择 "rme" 约束，因此它存储存和使用的存储器操作数。

夹一个是不是太慢，但它仍然是3uops在Skylake，有2个周期的延迟。这是伟大的在AMD Cpu，在那里饱和具有单个周期的延迟。(资料来源： 昂纳雾的指示表, 也可参看的 标签wiki x86性能链接)。它仍然是更好的比@sellibitze的版本，但比@Sheldon的顺序依赖的版本。(请参阅上的代码Godbolt)

但请记住，内联asm失败的优化喜欢恒的传播，因此，任何纯-C++版本将可以更好地在这种情况。

正确答案是...

(A&B)+((A^B)>>1)

你有什么是好的，与微小的细节，它将权利要求，平均3和3是2。我猜你不想；幸运的是，有一个简单的解决：

unsigned int average = a/2 + b/2 + (a & b & 1);

这只是颠簸的平均份的情况下，这两个部门被截断。

如果代码被用于嵌入式微，如果速度是至关重要的，大会语言可能是有帮助的。在许多微，结果加会自然进入进行标志和指令的存在为转变它回到一个登记册。在一只手臂，平均工作(资料来源和目的.在寄存器)可以做到在两个说明；任何C-语言等同可能会产率至少为5,并可能是一个公平的多。

顺便说一句，在机器用短字的大小，差异甚至更大。在一个8位PIC-18系列，平均为两个32位数字将采取的十二个指令。这样做的转移、增加和修正，将需要5说明每个转移，八个为增加，和八的修正，因此26(不是很有2.5倍的差异，但也许更重要的在绝对值而言)。

(((a&b << 1) + (a^b)) >> 1) 也是一个很好的方式。

礼貌: http://www.ragestorm.net/blogs/?p=29

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

预计平均==5.0为这个测试

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top