我的任务是设计一个满足这些要求的功能:
这是我的解决方案:
#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之间移植。
我不知道如何在计算过程中发生溢出,以及在使用此函数处理数组期间可能出现的其他错误。
更有经验的人可以给我他的意见吗?
好吧,我可以预见到一个问题:
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++;}}
实际上你在这里做了一个popcount(可以在gcc / clang上使用__builtin_popcount,或者在MSVC上使用__popcnt。它们是特定于编译器的,但通常归结为大多数CPU上的单个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;
}