寻找除以 2 的最快方法
Looking for the fastest way to divide by 2
我搜索了半天，发现了一些关于在 C++ 中使用定点数据类型和移位来完成除法运算同时避免浮点数学运算的非常有趣的事情。但是，我只能理解其中的一小部分，而且我似乎什么也做不了。
我只想取两个整数，将它们相加，然后除以二得到平均值。不过，我需要能够非常快地完成这项工作，因为我正在 Arduino 上插入相机像素数据，而且我还有其他操作要做。
所以我对一般的转变感到困惑。假设我要除以二的整数是 27。27 的一半是 13.5。但无论我尝试哪种定点数据类型，我都只能得到 13 作为输出。例如：
uint8_t x = 27;
Serial.println( x >> 1 );
returns 13
一定有一些简单的方法可以做到这一点，对吧？
不动点确实给了你一种表示 13.5 的方法。维基百科关于 Q 号格式的文章内容丰富：https://en.wikipedia.org/wiki/Q_(number_format)
这样想：您继续使用整数，但不是按表面值取整数，而是将它们隐含地除以 2 的幂以获得它们的语义值。
因此，如果使用无符号字节作为基本类型（值介于 0 和 255 之间，包括在内），您可能会隐式除以 2**3 (8)。现在要表示 27，您需要将整数设置为 27*8=>216。除以二，你向右移动一个；现在你的整数是 108，除以 8 的隐式分母得到 13.5，这是你期望的值。
当然，您必须意识到定点数系统（还有浮点数，虽然不太明显）仍然有局限性；无论您做什么，某些操作都会溢出，而某些操作会导致精度损失。这是使用有限大小类型的正常结果。
你只得到 13 的原因是因为你在位移时实际上切断了最低有效位。由于您正在切断它们，因此没有剩余物需要检查。如果您对您的余数感兴趣，您可以这样做：
uint8_t x = 27;
Serial.println((x - (x >> 1) - (x >> 1));
(x - (x >> 1)) 应该在这里给出 14。
一旦确定余数是否为 1，将数字加 .5 将非常简单。
Say the integer I want to divide by two is 27. Half of 27 is 13.5. But
no matter what fixed point data type I try, I can only get 13 as an
output.
来自维基百科定点算法：
The scaling factor is usually a power of 10 (for human convenience) or
a power of 2 (for computational efficiency).
您实际上提到了定点数据类型，我认为这是最好的方法。但无论你尝试了什么？也许我们对不动点算术有不同的理解。
while avoiding floating point math.
另一个有价值的目标，尽管价值有所降低。即使在嵌入式系统中，我也很少需要处理没有浮点部分的处理器。浮点硬件已经相当不错了。
无论如何，使用定点可以避免对浮点的任何需求。即使是为了展示目的。
我想我需要继续举几个例子。
定点示例 1：美元和便士
美国货币的单位是美元。美元 是 定点数据类型。
那么，如果你有 27 美元，你如何与你的兄弟姐妹平分？
大家都知道的（几种）方法之一是将 27 美元兑换成 2700 便士。将该值除以 2 是微不足道的。现在你和你的兄弟姐妹每人可以获得 1350 便士。 （即便士是定点数据类型，可以轻松转换 to/from 美元，反之亦然）
请注意，这完全是整数运算。添加 2 个整数，然后除以 2（任何现代编译器都会选择最快的实现方式……整数除法或可能右移 2），在我的桌面上，这 2 个操作只需不到一微秒即可完成。
您不应再浪费时间来衡量这两个选项（除法与右移）的相对性能，您只需在代码测试正确时启用 -O3。你的编译器应该可以正确选择。
任何问题中的单位选择都基于涵盖值范围（在您的问题中）的比例因子以及单位之间可理解且快速实现的转换。请注意 uint64_t 可以描述大量现金，即使是几美分。 （向学生发起挑战。）
总的来说，关于定点：
给定
uint8_t x = 27;
以及均匀快速地除以 2 的愿望......任何比例因子都可以满足您的需求吗？我说是。
示例 2 - 50 分硬币和 1 美元
我们试试看，例如，一个简单的比例因子 2，即单位是 hu，或半个单位。 （类似于 50 美分硬币）
uint8_t x = 27 * 1/hu; (hu = 1/2)
这意味着54 hu代表27个单位。 （即，需要 54 个 50 美分的硬币才能合计 27 美元）
定点解决方案是缩放整数值以实现所需的算术运算。如果缩放到偶数，所有整数将平均分配给 hu 单位。
示例 3 - 镍币和一美元
另一个可能的比例可能是 20，十进制（为了可读性）和二进制为了性能。 （注意一元有20镍币）
uint16 x = 27 * 1/tu; (tu = 1/20)
现在 540 代表缩放的 27。即 540 镍
所有示例都是完整的整数，提供准确的答案，并且有一个简单的机制来转换值以呈现给用户。即使用哪个固定点，转换为便士的模拟，因此 1350 便士。
将一分钱显示为一美元
std::cout << (pennyCount / 100) << "." << (pennyCount % 100) << std::endl;
我认为这应该类似于（未测试）
13.50
现在你的挑战是让它在输出上看起来漂亮。
以下应该有效并且应该很快：
float y = (x >> 1) + (0.5 * (x & 0x01))
它的作用
(x >> 1) 使用移位除以 2(0.5 * (x & 0x01))如果最后一位是1（奇数）则加0.5
我搜索了半天，发现了一些关于在 C++ 中使用定点数据类型和移位来完成除法运算同时避免浮点数学运算的非常有趣的事情。但是，我只能理解其中的一小部分，而且我似乎什么也做不了。
我只想取两个整数，将它们相加，然后除以二得到平均值。不过，我需要能够非常快地完成这项工作，因为我正在 Arduino 上插入相机像素数据，而且我还有其他操作要做。
所以我对一般的转变感到困惑。假设我要除以二的整数是 27。27 的一半是 13.5。但无论我尝试哪种定点数据类型，我都只能得到 13 作为输出。例如：
uint8_t x = 27;
Serial.println( x >> 1 );
returns 13
一定有一些简单的方法可以做到这一点，对吧？
不动点确实给了你一种表示 13.5 的方法。维基百科关于 Q 号格式的文章内容丰富：https://en.wikipedia.org/wiki/Q_(number_format)
这样想：您继续使用整数，但不是按表面值取整数，而是将它们隐含地除以 2 的幂以获得它们的语义值。
因此，如果使用无符号字节作为基本类型（值介于 0 和 255 之间，包括在内），您可能会隐式除以 2**3 (8)。现在要表示 27，您需要将整数设置为 27*8=>216。除以二，你向右移动一个；现在你的整数是 108，除以 8 的隐式分母得到 13.5，这是你期望的值。
当然，您必须意识到定点数系统（还有浮点数，虽然不太明显）仍然有局限性；无论您做什么，某些操作都会溢出，而某些操作会导致精度损失。这是使用有限大小类型的正常结果。
你只得到 13 的原因是因为你在位移时实际上切断了最低有效位。由于您正在切断它们，因此没有剩余物需要检查。如果您对您的余数感兴趣，您可以这样做：
uint8_t x = 27;
Serial.println((x - (x >> 1) - (x >> 1));
(x - (x >> 1)) 应该在这里给出 14。
一旦确定余数是否为 1，将数字加 .5 将非常简单。
Say the integer I want to divide by two is 27. Half of 27 is 13.5. But no matter what fixed point data type I try, I can only get 13 as an output.
来自维基百科定点算法：
The scaling factor is usually a power of 10 (for human convenience) or a power of 2 (for computational efficiency).
您实际上提到了定点数据类型，我认为这是最好的方法。但无论你尝试了什么？也许我们对不动点算术有不同的理解。
while avoiding floating point math.
另一个有价值的目标，尽管价值有所降低。即使在嵌入式系统中，我也很少需要处理没有浮点部分的处理器。浮点硬件已经相当不错了。
无论如何，使用定点可以避免对浮点的任何需求。即使是为了展示目的。
我想我需要继续举几个例子。
定点示例 1：美元和便士
美国货币的单位是美元。美元 是 定点数据类型。
那么，如果你有 27 美元，你如何与你的兄弟姐妹平分？
大家都知道的（几种）方法之一是将 27 美元兑换成 2700 便士。将该值除以 2 是微不足道的。现在你和你的兄弟姐妹每人可以获得 1350 便士。 （即便士是定点数据类型，可以轻松转换 to/from 美元，反之亦然）
请注意，这完全是整数运算。添加 2 个整数，然后除以 2（任何现代编译器都会选择最快的实现方式……整数除法或可能右移 2），在我的桌面上，这 2 个操作只需不到一微秒即可完成。
您不应再浪费时间来衡量这两个选项（除法与右移）的相对性能，您只需在代码测试正确时启用 -O3。你的编译器应该可以正确选择。
任何问题中的单位选择都基于涵盖值范围（在您的问题中）的比例因子以及单位之间可理解且快速实现的转换。请注意 uint64_t 可以描述大量现金，即使是几美分。 （向学生发起挑战。）
总的来说，关于定点：
给定
uint8_t x = 27;
以及均匀快速地除以 2 的愿望......任何比例因子都可以满足您的需求吗？我说是。
示例 2 - 50 分硬币和 1 美元
我们试试看，例如，一个简单的比例因子 2，即单位是 hu，或半个单位。 （类似于 50 美分硬币）
uint8_t x = 27 * 1/hu; (hu = 1/2)
这意味着54 hu代表27个单位。 （即，需要 54 个 50 美分的硬币才能合计 27 美元）
定点解决方案是缩放整数值以实现所需的算术运算。如果缩放到偶数，所有整数将平均分配给 hu 单位。
示例 3 - 镍币和一美元
另一个可能的比例可能是 20，十进制（为了可读性）和二进制为了性能。 （注意一元有20镍币）
uint16 x = 27 * 1/tu; (tu = 1/20)
现在 540 代表缩放的 27。即 540 镍
所有示例都是完整的整数，提供准确的答案，并且有一个简单的机制来转换值以呈现给用户。即使用哪个固定点，转换为便士的模拟，因此 1350 便士。
将一分钱显示为一美元
std::cout << (pennyCount / 100) << "." << (pennyCount % 100) << std::endl;
我认为这应该类似于（未测试）
13.50
现在你的挑战是让它在输出上看起来漂亮。
以下应该有效并且应该很快：
float y = (x >> 1) + (0.5 * (x & 0x01))
它的作用
(x >> 1)使用移位除以 2(0.5 * (x & 0x01))如果最后一位是1（奇数）则加0.5