Проверка частично известного целого лежит в пределах диапазона


У меня есть особая проблема, для которой я ищу эффективное решение. У меня есть массив байтов, который содержит наиболее значимые n байтов беззнакового 4-байтового целого числа (самый первый байт sig). Значение оставшихся байтов (если таковые имеются) неизвестно. Мне нужно проверить, может ли частично известное целое число попасть в определенный диапазон (+или - x) известного целого числа. Это также допустимо для целого числа, представленного тестируемым массивом байтов, чтобы обернуть его.

У меня есть решение который работает (ниже). Проблема в том, что это решение выполняет намного больше сравнений, чем я считаю необходимым, и вся нагрузка сравнений будет дублироваться в сценарии, в котором неизвестны наименьшие байты sig. Я почти уверен, что это можно сделать более эффективно, но не могу понять, как. Сценарий, в котором наименее значимые байты неизвестны, является пограничным случаем, поэтому я мог бы жить с ним, но он является частью системы, которая должна иметь низкую задержку, так что если кто-то может помочь с этим это было бы здорово.

Заранее благодарю.

static final int BYTES_IN_INT = 4;
static final int BYTE_SHIFT = 010;

// partial integer byte array length guaranteed to be 1-4 so no checking necessary
static boolean checkPartialIntegerInRange(byte[] partialIntegerBytes, int expectedValue, int range)
{
   boolean inRange = false;

   if(partialIntegerBytes.length == BYTES_IN_INT)
   {
      // normal scenario, all bytes known
      inRange = Math.abs(ByteBuffer.wrap(partialIntegerBytes).getInt() - expectedValue) <= range;
   }
   else
   {
      // we don't know least significant bytes, could have any value
      // need to check if partially known int could lie in the range
      int partialInteger = 0;
      int mask = 0;

      // build partial int and mask
      for (int i = 0; i < partialIntegerBytes.length; i++)
      {
         int shift = ((BYTES_IN_INT - 1) - i) * BYTE_SHIFT;
         // shift bytes to correct position
         partialInteger |= (partialIntegerBytes[i] << shift);

         // build up mask to mask off expected value for comparison
         mask |= (0xFF << shift);
      }

      // check partial int falls in range
      for (int i = -(range); i <= range; i++)
      {
         if (partialInteger == ((expectedValue + i) & mask))
         {
            inRange = true;
            break;
         }
      }
   }
   return inRange;
}

EDIT: спасибо авторам ниже. Вот мое новое решение. Комментарии приветствуются.

static final int  BYTES_IN_INT = 4;
static final int  BYTE_SHIFT = 010;
static final int  UBYTE_MASK = 0xFF;
static final long UINT_MASK = 0xFFFFFFFFl;

public static boolean checkPartialIntegerInRange(byte[] partialIntegerBytes, int expectedValue, int range)
{
  boolean inRange;

  if(partialIntegerBytes.length == BYTES_IN_INT)
  {
    inRange = Math.abs(ByteBuffer.wrap(partialIntegerBytes).getInt() - expectedValue) <= range;
  }
  else
  {
    int partialIntegerMin = 0;
    int partialIntegerMax = 0;

    for(int i=0; i < BYTES_IN_INT; i++)
    {
      int shift = ((BYTES_IN_INT - 1) - i) * BYTE_SHIFT;
      if(i < partialIntegerBytes.length)
      {
        partialIntegerMin |= (((partialIntegerBytes[i] & UBYTE_MASK) << shift));
        partialIntegerMax = partialIntegerMin;
      }
      else
      {
        partialIntegerMax |=(UBYTE_MASK << shift);
      }
    }

    long partialMinUnsigned = partialIntegerMin & UINT_MASK;
    long partialMaxUnsigned = partialIntegerMax & UINT_MASK;
    long rangeMinUnsigned = (expectedValue - range) & UINT_MASK;
    long rangeMaxUnsigned = (expectedValue + range) & UINT_MASK;

    if(rangeMinUnsigned <= rangeMaxUnsigned)
    {
      inRange = partialMinUnsigned <= rangeMaxUnsigned && partialMaxUnsigned >= rangeMinUnsigned;
    }
    else
    {
      inRange = partialMinUnsigned <= rangeMaxUnsigned || partialMaxUnsigned >= rangeMinUnsigned;
    }
  }
  return inRange;
}
2 2

2 ответа:

Предположим, что у вас есть один интервал по часовой стрелке (x, y) и один нормальный интервал (low, high) (каждый из которых включает свои конечные точки), определяя, пересекаются ли они, можно сделать так (не проверено):

if (x <= y) {
    // (x, y) is a normal interval, use normal interval intersect
    return low <= y && high >= x;
}
else {
    // (x, y) wraps
    return low <= y || high >= x;
}

Для сравнения целых чисел без знака можно использовать longs (приведение к x & 0xffffffffL для противодействия расширению знака) или Integer.compareUnsigned (в более новых версиях Java) или, если вы предпочитаете, вы можете добавить/вычесть/xor оба операнда с Integer.MIN_VALUE.

Преобразуйте неподписанные байты в целое число. Сдвиг вправо на 32-n (так что ваши значимые байты-это мин байты). Вправо-сдвиньте ваши мин / макс целые числа на ту же величину. Если ваше сдвинутое тестовое значение равно любому сдвинутому целому числу, оно может находиться в этом диапазоне. Если это между ними, то определенно в пределах досягаемости.

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