Ближайший / самый быстрый алгоритм для наименьшего положительного числа

Question

Простой вопрос. Какой самый удобный способ получить в c ++ какое из двух чисел (u0 и u1) является наименьшим положительным числом? (это все еще эффективно)

Каждый способ, которым я пытаюсь это сделать, включает в себя большие операторы if или сложные условные операторы.

Спасибо, Dan

Вот простой пример:

bool lowestPositive(int a, int b, int& result)
{
    //checking code
    result = b;
    return true;
}


lowestPositive(5, 6, result);

Answer 1

Если значения представлены в двух дополнениях, то

result = ((unsigned )a < (unsigned )b) ? a : b;

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

return result >= 0;

Answer 2

Я предпочитаю ясность, а не компактность:

bool lowestPositive( int a, int b, int& result )
{
   if (a > 0 && a <= b) // a is positive and smaller than or equal to b
      result = a;
   else if (b > 0) // b is positive and either smaller than a or a is negative
      result = b;
   else
      result = a; // at least b is negative, we might not have an answer

   return result > 0;  // zero is not positive
}

Answer 3

Вот быстрое решение на C, использующее bit twiddling , чтобы найти min(x, y). Это модифицированная версия @ ответа Дуга Керри , вдохновленная ответом на Найти минимальное положительное значение вопрос:

bool lowestPositive(int a, int b, int* pout)
{
  /* exclude zero, make a negative number to be larger any positive number */
  unsigned x = (a - 1), y = (b - 1);    
  /* min(x, y) + 1 */
  *pout = y + ((x - y) & -(x < y)) + 1; 
  return *pout > 0;
}

Пример:

/** gcc -std=c99 *.c && a */
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdbool.h>

void T(int a, int b) 
{           
  int result = 0;   
  printf("%d %d ", a, b);       
  if (lowestPositive(a, b, &result))    
    printf(": %d\n", result);       
  else              
    printf(" are not positive\n");  
}

int main(int argc, char *argv[])
{
  T(5, 6);
  T(6, 5);
  T(6, -1);
  T(-1, -2);

  T(INT_MIN, INT_MAX);
  T(INT_MIN, INT_MIN);
  T(INT_MAX, INT_MIN);
  T(0, -1);
  T(0, INT_MIN);
  T(-1, 0);
  T(INT_MIN, 0);
  T(INT_MAX, 0);
  T(0, INT_MAX);
  T(0, 0);

  return 0;
}

Выход:

5 6 : 5
6 5 : 5
6 -1 : 6
-1 -2  are not positive
-2147483648 2147483647 : 2147483647
-2147483648 -2147483648  are not positive
2147483647 -2147483648 : 2147483647
0 -1  are not positive
0 -2147483648  are not positive
-1 0  are not positive
-2147483648 0  are not positive
2147483647 0 : 2147483647
0 2147483647 : 2147483647
0 0  are not positive

Answer 4

Может быть, меня унизят, но только для ударов, вот результат без каких-либо сравнений, потому что сравнения для кнутов. : -)

bool lowestPositive(int u, int v, int& result)
{
  result = (u + v - abs(u - v))/2;
  return (bool) result - (u + v + abs(u - v)) / 2;
}

Примечание. Сбой, если (u + v)> max_int. Для правильного кода возврата должен быть хотя бы один номер. Также благодарю решение Polythinker:)

Answer 5

unsigned int mask = 1 << 31;
unsigned int m = mask;
while ((a & m) == (b & m)) {
  m >>= 1;
}
result = (a & m) ? b : a;
return ! ((a & mask) && (b & mask));

РЕДАКТИРОВАТЬ: думал, что это не так интересно, поэтому я удалил его. Но, если подумать, просто оставьте это здесь для развлечения :) Это можно рассматривать как дамповую версию ответа Дуга:)

Answer 6

тонн ответов здесь игнорируют тот факт, что ноль не является положительным:)

с хитрым литьем и крачкой:

bool leastPositive(int a, int b, int& result) {
    result = ((unsigned) a < (unsigned) b) ? a : b;
    return result > 0;
}

менее мило:

bool leastPositive(int a, int b, int& result) {
    if(a > 0 && b > 0)
        result = a < b ? a : b;
    else
        result = a > b ? a : b:
    return result > 0;
}

Answer 7

Это будет обрабатывать все возможные вводы по вашему запросу.

bool lowestPositive(int a, int b, int& result)
{
    if ( a < 0 and b < 0 )
        return false

    result = std::min<unsigned int>( a, b );
    return true;
}

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

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

boost::optional<int> lowestPositive(int a, int b)
{
    boost::optional<int> result;
    if ( a >= 0 or b >= 0 )
        result = std::min<unsigned int>( a, b );
    return result;
}

или

void lowestPositive(int a, int b, int& result, bool &success)
{
    success = ( a >= 0 or b >= 0 )

    if ( success )
        result = std::min<unsigned int>( a, b );
}

Answer 8

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

unsigned int minUnsigned( unsigned int a, unsigned int b )
{
   return ( a < b ) ? a : b;
}

bool lowestPositive( int a, int b, int& result )
{
   if ( a < 0 && b < 0 )  // SO comments refer to the previous version that had || here
   {
       return false;
   }

   result = minUnsigned( (unsigned)a, (unsigned)b );  // negative signed integers become large unsigned values
   return true;
}

Это работает для всех трех представлений со знаком и целыми числами, разрешенных ISO C: дополнение двух, одно дополнение и даже знак / величина. Все, что нас волнует, это то, что любое целое число с положительной подписью (очищенное MSB) сравнивается ниже любого значения с набором MSB.

Это на самом деле компилируется в действительно хороший код с clang для x86, как , который вы можете увидеть в Godbolt Compiler Explorer . gcc 5.3 к сожалению делает намного хуже .

Answer 9

Без умов, разумной ясности, работает для целых чисел и поплавков:

template<class T>
  inline
  bool LowestPositive( const T a, const T b, T* result ) {
  const bool b_is_pos = b > 0;
  if( a > 0 && ( !b_is_pos || a < b ) ) { 
    *result = a;
    return true;
  }
  if( b_is_pos ) {
    *result = b; 
    return true;
  }
  return false;
}

• Обратите внимание, что 0 (ноль) не является положительным числом.
• ОП запрашивает работу с числами (я интерпретирую это как целые числа и с плавающей точкой).
• Указатель результата разыменования только при наличии положительного результата (производительность)
• Только a и b тестируйте на положительность один раз (производительность - не уверены, стоит ли такой тест дорого?)

Обратите внимание, что принятый ответ (от tvanfosson) неверен . Сбой, если а положительный, а б отрицательный (говорит, что «ни один не положительный»). (Это единственная причина, по которой я добавляю отдельный ответ - у меня недостаточно репутации, чтобы добавлять комментарии.)

Answer 10

uint lowestPos(uint a, uint b) { return (a < b ? a : b); }

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

Предварительным условием является то, что они не равны, вы должны использовать это следующим образом:

if (a == b)
  cout << "equal";
else
{
  uint lowest = lowestPos(a, b);
  cout << (lowest == a ? "a is lowest" : "b is lowest");
}

Вы можете ввести const, если хотите предотвратить изменения или ссылки, если хотите изменить результат. В нормальных условиях компьютер оптимизирует и даже встроит функцию.