在不同 CPU 上处理整数

Question

我的任务是设计一个满足这些要求的函数：

1. 函数应将给定一维数组的成员相加。 但是，它应该只对二进制表示中的 1 数高于定义阈值的成员求和(例如，如果阈值为 4，则将计算数字 255，而 15 将不计算)
2. 数组长度是任意的
3. 该函数应使用尽可能少的内存，并应以有效的方式编写
4. 生产函数代码('sum_filtered(){..}')不得使用任何标准C库函数(或任何其他库)
5. 该函数在成功时返回 0，在错误时返回错误代码
6. 数组元素的类型为 16 位有符号整数，计算过程中溢出应视为失败
7. 使用确保不同CPU之间可移植性的数据类型(因此计算在8/16/32位MCU上是相同的)
8. 函数代码应在 doxygen 注释中包含合理数量的注释

这是我的解决方案：

#include <iostream>
using namespace std;
int sum_filtered(short array[], int treshold)
{
// return 1 if invalid input parameters
if((treshold < 0) || (treshold > 16)){return(1);}
int sum = 0;
int bitcnt = 0;
for(int i=0; i < sizeof(array); i++)
{
// Count one bits of integer
bitcnt = 0;
for (int pos = 0 ; pos < 16 ; pos++) {if (array[i] & (1 << pos)) {bitcnt++;}}
// Add integer to sum if bitcnt>treshold
if(bitcnt>treshold){sum += array[i];}
}
return(0);
}
int main()
{
short array[5] = {15, 2652, 14, 1562, -115324};
int result = sum_filtered(array, 14);
cout << result << endl;
short array2[5] = {15, 2652, 14, 1562, 15324};
result = sum_filtered(array2, -2);
cout << result << endl;
}

但是，我不确定此代码是否可以在不同CPU之间移植。

而且我不知道在计算过程中如何发生溢出，以及在使用此函数处理数组期间可能出现的其他错误。

更有经验的人可以给我他的意见吗？

Answer 1

好吧，我可以预见一个问题：

for(int i=0; i < sizeof(array); i++)

在此上下文中，数组是一个指针，因此在 32 位系统上可能是 4，在 64 位系统上可能是 8。您确实希望将计数变量(在本例中为 5)传递到 sum_filtered 函数中(然后您可以将计数作为 sizeof(array)/sizeof(short))。

无论如何，这段代码：

// Count one bits of integer
bitcnt = 0;
for (int pos = 0 ; pos < 16 ; pos++) {if (array[i] & (1 << pos)) {bitcnt++;}}

实际上，您正在这里进行pop计数(可以在gcc/clang上使用__builtin_popcount或在MSVC上使用__popcnt来完成。它们是特定于编译器的，但通常归结为大多数 CPU 上的单个弹出计数 CPU 指令)。

如果您确实想以慢速方式执行此操作，那么一种有效的方法是将计算视为按位 SIMD 操作的一种形式：

#include <cstdint> // or stdint.h if you have a rubbish compiler :)
uint16_t popcount(uint16_t s)
{
// perform 8x 1bit adds
uint16_t a0 =  s & 0x5555;
uint16_t b0 = (s >> 1) & 0x5555;
uint16_t s0 = a0 + b0;
// perform 4x 2bit adds
uint16_t a1 =  s0 & 0x3333;
uint16_t b1 = (s0 >> 2) & 0x3333;
uint16_t s1 = a1 + b1;
// perform 2x 4bit adds
uint16_t a2 =  s1 & 0x0F0F;
uint16_t b2 = (s1 >> 4) & 0x0F0F;
uint16_t s2 = a2 + b2;
// perform 1x 8bit adds
uint16_t a3 =  s2 & 0x00FF;
uint16_t b3 = (s2 >> 8) & 0x00FF;
return a3 + b3;
}

我知道它说你不能使用 stdlib 函数(你的第 4 点)，但这肯定不适用于标准化的整数类型吗？(例如uint16_t)如果是这样，那么就没有办法保证跨平台的可移植性。你倒霉了。

就个人而言，我只使用64位整数作为总和。这应该会降低任何溢出的风险*(即，如果阈值为零，并且所有值均为 -128，那么如果数组大小超过 0x1FFFFFFFFFFFF 个元素(十进制为 562,949,953,421,311)，则会溢出。

#include <cstdint>
int64_t sum_filtered(int16_t array[], uint16_t threshold, size_t array_length)
{
// changing the type on threshold to be unsigned means we don't need to test
// for negative numbers. 
if(threshold > 16) { return 1; }
int64_t sum = 0;
for(size_t i=0; i < array_length; i++)
{
if (popcount(array[i]) > threshold) 
{
sum += array[i];
}
}
return sum;
}