Эффективный способ определения минимального размера поля, необходимого для хранения отклонений при вводе пользователем

Question

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

Я получаю от пользователя ввод нескольких 32-битных целых чисел.Например, пользователь может ввести следующие значения (показаны в шестнадцатеричном виде для простоты объяснения):

0x00001234
0x00005678
0x0000abcd

В этом конкретном случае первые 2 байта каждого ввода являются постоянными, а последние 2 байта являютсяпеременная.В целях эффективности я мог бы хранить 0x0000 как одну константу и создать вектор значений uint16_t для хранения переменной части ввода (0x1234, 0x5678, 0xabcd).

Теперь предположим, что пользователь вводит следующее:

0x00000234
0x56780000
0x00001000

В этом случае мне понадобится вектор значений uint32_t для хранения переменной части ввода, поскольку каждое значение влияет на разные байты.

---

Моя текущая мысль состоит в том, чтобы сделать следующее:

uint32_t myVal = 0;
myVal |= input1;
myVal |= input2;
// ...

И затем в конце найти расстояние между первым и последним битом "переключенным" (т. Е. 1) в myVal.Это расстояние даст мне требуемый размер поля для переменной части всех входов.

Однако это не похоже на то, как если бы оно подходило для большого количества пользовательских входов.Какие-нибудь рекомендации относительно элегантного и эффективного способа определения этого?

---

Обновление:

Я упростил проблему в своем объяснении выше.

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

Таким образом, компонент A обеспечиваетКомпонент B в моей системе со значениями.Иногда эти значения являются 128-битными, но компонент B поддерживает только 32-битные значения.

Если переменная часть 128-битного значения может быть выражена 32-битным значением, я могу принять это.В противном случае мне придется отклонить его с ошибкой.

Я не в состоянии изменить компонент B, чтобы разрешить 128-битные значения, или изменить компонент A, чтобы предотвратить его использование 128-битных значений (тамаппаратные ограничения здесь тоже).

Answer 1

Сохраните первое полное 128-разрядное число, с которым вы столкнетесь, затем вставьте 32-разрядные младшие разряды в вектор, установите bool reject_all = false. Для каждого оставшегося числа, если старшие (128-32 = 96) биты отличаются от первого числа, затем установите reject_all = true, в противном случае вставьте свои младшие биты в вектор. В конце цикла используйте reject_all, чтобы решить, следует ли использовать вектор значений.

Answer 2

Хотя я не вижу причины для всего этого ... Почему бы просто не сравнить вход с std::numeric_limits<uint16_t>::max()?Если вход дает большее значение, тогда вам нужно использовать uint32_t.

---

. Отвечая на ваши изменения:

Полагаю, для повышения производительности вы должны использовать специфичные для оборудования инструкции низкого уровня.Вы можете перебрать 32-битные части входного 128-битного значения, а затем добавить каждую из них к некоторой переменной и проверить разницу между следующим значением и текущей суммой.Если разница не равна сумме, вы должны пропустить это 128-битное значение, иначе вы получите необходимый результат в конце.Ниже приведен пример:

uint32_t get_value( uint32_t v1, uint32_t v2, uint32_t v3, uint32_t v4)
{
  uint32_t temp = v1; 
  if ( temp - v2 != temp ) throw exception;
  temp += v2; if ( temp - v3 != temp ) throw exception;
  temp += v3; if ( temp - v4 != temp ) throw exception;
  temp = v4;
  return temp;
}

В этом примере C ++ это может выглядеть глупо, но я верю, что в ассемблерном коде это должно эффективно обработать входной поток.

Answer 3

Используйте

uint32_t ORVal = 0;
uint32_t ANDVal = 0xFFFFFFFF;

ORVal  |= input1;
ANDVal &= input1;
ORVal  |= input2;
ANDVal &= input2;
ORVal  |= input3;
ANDVal &= input3; // etc.

// At end of input...
mask = ORVal ^ ANDVal; 
// bit positions set to 0 were constant, bit positions set to 1 changed

Битовая позиция в ORVal будет 1, если хотя бы один вход имел 1 в этой позиции, и 0, если ВСЕ входы имели 0 в этой позиции. Битовая позиция в ANDVal будет 0, если хотя бы один вход имел 0 в этой битовой позиции и 1, если ВСЕ входы имели 1 в этой позиции.

Если битовая позиция на входах всегда была 1, тогда ORVal и ANDVal будут установлены на 1. Если битовая позиция на входах всегда была 0, тогда ORVal и ANDVal будут установлены на 0. Если в битовой позиции был микс 0 и 1, тогда ORVal будет установлен на 1, а ANDVal установлен на 0, следовательно, XOR в конце дает маску для битовые позиции, которые изменились.

Answer 4

Похоже, вам нужно придумать кумулятивную битовую маску - которую вы затем можете посмотреть, чтобы увидеть, есть ли у вас концевые или ведущие постоянные биты.Потребуется алгоритм, который работает с каждым входом (что делает его алгоритмом O (n), где n - число проверяемых значений).

Алгоритм будет похож на то, что вы ужеdone:

unsigned long long bitmask = 0uL;
std::size_t count = val.size();
for (std::size_t i = 0; i < count; ++i)
  bitmask |= val[i];

Затем вы можете проверить, сколько бит / байтов можно сделать постоянными, и собираетесь ли вы использовать полные 32 бита.Если у вас есть доступ к инструкциям SSE, вы можете векторизовать это с помощью OpenMP.

Также возможна оптимизация путем короткого замыкания, чтобы увидеть, является ли расстояние между первым 1 битом и последним 1 битомуже больше 32, и в этом случае вы можете остановиться.

Для лучшего масштабирования этого алгоритма вам придется делать это параллельно.Ваш друг будет заниматься векторной обработкой (возможно, с использованием CUDA для графических процессоров Nvidia или OpenCL, если вы работаете на Mac или на платформах, которые уже поддерживают OpenCL, или просто аннотациями OpenMP).

Answer 5

Самый эффективный способ сохранить ряд целых чисел без знака в диапазоне [0, (2^32)-1] - это просто использовать uint32_t.Прыжки по обручам для сохранения 2 байтов из пользовательского ввода не стоят вашего времени - пользователь при своей жизни не может ввести достаточно целых чисел, чтобы ваш код начал их сжимать.Он или она умрет от старости задолго до того, как ограничения памяти станут очевидными в любой современной системе.