相关疑难解决方法(0)

你会如何除以3为数字,没有使用*,/,+,-,%,运营商？

号码可以是签名或未签名.

有一个现有的问题“3 个长整数的平均值”，它特别关注三个有符号整数的平均值的有效计算。

然而，无符号整数的使用允许额外的优化不适用于上一个问题中涵盖的场景。这个问题是关于三个无符号整数的平均值的有效计算，其中平均值向零舍入，即在数学术语中我想计算？(a + b + c) / 3 ?。

计算此平均值的一种直接方法是

 avg = a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3;

首先，现代优化编译器会将除法转换为具有倒数加移位的乘法，并将模运算转换为反向乘法和减法，其中反向乘法可能使用许多体系结构上可用的scale_add习语，例如leax86_64的，add用lsl #n在ARM，iscadd在NVIDIA GPU。

在尝试以适用于许多常见平台的通用方式优化上述内容时，我观察到整数运算的成本通常在逻辑关系中？（添加|子）？转移？规模_添加？MUL。这里的成本是指所有延迟、吞吐量限制和功耗。当处理的整数类型比本地寄存器宽度更宽时，例如在uint64_t32 位处理器上处理数据时，任何此类差异都会变得更加明显。

因此，我的优化策略是尽量减少指令数量，并在可能的情况下用“廉价”操作替换“昂贵”操作，同时不增加寄存器压力并为宽无序处理器保留可利用的并行性。

第一个观察结果是，我们可以通过首先应用产生和值和进位值的 CSA（进位保存加法器）将三个操作数的和减少为两个操作数的和，其中进位值的权重是和的两倍价值。在大多数处理器上，基于软件的 CSA 的成本是五个逻辑s。一些处理器，如 …

如何计算整数除法2 ⁶⁴ / n？假设：

• unsigned long 是64位
• 我们使用64位CPU
• 1 <n <2 ⁶⁴

如果这样做18446744073709551616ul / n，我们将warning: integer constant is too large for its type在编译时到达。这是因为我们无法在64位CPU中表示2 ⁶⁴。另一种方法如下：

#define IS_POWER_OF_TWO(x) ((x & (x - 1)) == 0)

unsigned long q = 18446744073709551615ul / n;
if (IS_POWER_OF_TWO(n))
    return q + 1;
else
    return q;

是否有更快的（CPU周期）或更干净的（编码）实现？