在不同 CPU 上处理整数

Question

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

函数对给定的一维数组的成员求和。但是，它应该只对二进制表示中 1 的数量高于定义的阈值的成员求和（例如，如果阈值为 4，则将计算数字 255，而不会计算 15）
数组长度任意
该函数应使用尽可能少的内存，并应以高效的方式编写
生产函数代码（‘sum_filtered(){..}’）不得使用任何标准 C 库函数（或任何其他库）
函数应 return 成功时为 0，错误时应为错误代码
数组元素为16位有符号整数类型，计算时溢出视为失败
使用确保不同 CPU 之间可移植性的数据类型（因此计算在 8/16/32 位 MCU 上是相同的）
函数代码应该在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++;}}

实际上你在这里做了一个弹出计数 （可以使用 gcc/clang 上的 __builtin_popcount 或 MSVC 上的 __popcnt 来完成。它们是特定于编译器的，但是通常在大多数 CPUs) 上归结为单个 popcount 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;
}

在不同 CPU 上处理整数

Processing of integers on different CPUs

c++

integer-overflow