Обработка целых чисел на разных процессорах - PullRequest
Новая
       19

Обработка целых чисел на разных процессорах

0 голосов
/ 23 апреля 2019

Моя задача - разработать функцию, которая удовлетворяет этим требованиям:

  1. Функция должна суммировать элементы данного одномерного массива.Однако он должен суммировать только те элементы, число единиц в двоичном представлении которых превышает определенный порог (например, если порог равен 4, число 255 будет подсчитано, а 15 - нет)
  2. Длина массива произвольна
  3. Функция должна использовать как можно меньше памяти и должна быть написана эффективным способом
  4. Код производственной функции ('sum_filtered () {..}') не должен использовать какую-либо стандартную библиотеку Cфункции (или любые другие библиотеки)
  5. Функция должна возвращать 0 при успехе и код ошибки при ошибке
  6. Элементы массива имеют тип 16-битовое целое число со знаком, и переполнение во время вычисления должно бытьрассматривается как сбой
  7. Используйте типы данных, обеспечивающие переносимость между разными ЦП (поэтому вычисления будут одинаковыми для 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;
}

Однако яне уверен, переносим ли этот код между разными процессорами.

И я не знаю, как может произойти переполнение во время вычислений и какие могут быть другие ошибки при обработке массивов с помощью этой функции.

Может ли кто-нибудь более опытный дать мне свое мнение?

1 Ответ

1 голос
/ 23 апреля 2019

Хорошо, я могу предвидеть одну проблему: массив 

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

в этом контексте является указателем, поэтому, скорее всего, будет 4 в 32-битных системах или 8 в 64-битных системах.Вы действительно хотите передать переменную count (в данном случае 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++;}}

Эффективно вы делаете здесь поп-учет (что можно сделать с помощью __builtin_popcount в gcc / clang или __popcnt в MSVC. Они являются компиляторомспецифические, но обычно сводятся к одной инструкции процессора поп-счет на большинстве процессоров) .

Если вы хотите сделать это медленным способом, то эффективный подход заключается в том, чтобы рассматривать вычисления как форму побитовой операции 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;
}

Я знаю, что это говорит, что вы можете 't использовать функции 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;
}
...