Самый опрятный / Самый Быстрый Алгоритм для Самого маленького Положительного числа

После того, как мое первое сообщение было отклонено, позвольте мне предполагать преждевременную оптимизацию проблемы, и Вы не должны волноваться о наличии большого количества из если операторы. Код, который Вы пишете естественно, требует нескольких, 'если' операторы, и выражаются ли они троичным если оператор (A? B: C) или классик, если блоки, время выполнения является тем же, компилятор собирается оптимизировать почти весь код, отправленный в очень почти ту же логику.

Интересуйтесь удобочитаемостью и надежностью Вашего кода вместо того, чтобы пытаться обмануть Ваше будущее сам или кто-либо еще, кто читает код. Каждым отправленным решением является O (1) от того, что я могу сказать, то есть, каждое решение будет способствовать незначительно производительности Вашего кода.

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

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

• минута <= 0 и макс. <= 0
• минута <= 0 и макс.> 0
• минута> 0 и макс.> 0

Лучшая вещь состоит в том, что это не взгляд, также сложный. Код:

bool lowestPositive(int a, int b, int& result)
{
    int min = (a < b) ? a : b;
    int max = (a > b) ? a : b;

    bool smin = min > 0;
    bool smax = max > 0;

    if(!smax) return false;

    if(smin) result = min;
    else result = max;

    return true;
}

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

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

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

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

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

Три строки с использованием (злоупотребление?) тернарного оператора

int *smallest_positive(int *u1, int *u2) {
    if (*u1 < 0) return *u2 >= 0 ? u2 : NULL;
    if (*u2 < 0) return u1;
    return *u1 < *u2 ? u1 : u2;
}

Не знайте об эффективности или что сделать, если и u1 и u2 отрицательны. Я решил возвратить ПУСТОЙ УКАЗАТЕЛЬ (который должен быть проверен в вызывающей стороне); возврат указателя на статический-1 мог бы быть более полезным.

Отредактированный для отражения изменений в исходном вопросе :)

bool smallest_positive(int u1, int u2, int& result) {
    if (u1 < 0) {
        if (u2 < 0) return false; /* result unchanged */
        result = u2;
    } else {
        if (u2 < 0) result = u1;
        else result = u1 < u2 ? u1 : u2;
    }
    return true;
}

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

• Некоторые программисты используют соглашение о присвоении имен в который продвижение u подразумевает неподписанный, но Вы не заявили явно, не подписаны ли Ваши "числа" или со знаком (или, в этом отношении, предполагается ли они как даже, являются неотъемлемой частью!)

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

• Описание также не определяет необходимое поведение, если оба значения неположительны.

• Наконец, некоторые ответы, предлагаемые до этого сообщения, кажется, подразумевают, что респондент думал (по ошибке), что 0 положительно! Оператор более конкретных требований мог бы помочь предотвратить любое недоразумение (или проясните, что проблема нуля не была продумана полностью, когда требование было записано).

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

Взлом с помощью "волшебную константу"-1:

enum
{
    INVALID_POSITIVE = -1
};

int lowestPositive(int a, int b)
{
    return (a>=0 ? ( b>=0 ? (b > a ? a : b ) : INVALID_POSITIVE ) : INVALID_POSITIVE );
}

Это не делает предположений о числах, являющихся положительным.

Псевдокод, потому что у меня нет компилятора под рукой:

////0 if both negative, 1 if u0 positive, 2 if u1 positive, 3 if both positive
switch((u0 > 0 ? 1 : 0) + (u1 > 0 ? 2 : 0)) {
  case 0:
    return false; //Note that this leaves the result value undef.
  case 1:
    result = u0;
    return true;
  case 2:
    result = u1;
    return true;
  case 3:
    result = (u0 < u1 ? u0 : u1);
    return true;
  default: //undefined and probably impossible condition
    return false;
}

Это компактно, без большого количества из если операторы, но полагается на троичное "?: "оператор, который является просто компактным если, то, еще оператор". (верный? "да": "нет")", возвращает "да", "(ложь? "да": "нет"), возвращает "нет".

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

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

с хитрым кастингом и крачкой:

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;
}

Это обработает все возможные исходные данные, как Вы запрашиваете.

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 );
}

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));

Править: Мысль это не настолько интересно, таким образом, я удалил его. Но на долгом размышлении, просто оставьте его здесь для забавы :) Это можно рассмотреть как версию дампа ответа Doug :)

Вот является быстрое решение в C использованием битового жонглирования для нахождения min(x, y). Это - измененная версия ответа @Doug Currie и вдохновленный ответом на Находку Минимальный Положительный вопрос о Значении:

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

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

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. По крайней мере одно число должно быть положительным, чтобы код возврата был корректен. Также благодарность решению полимыслителя :)

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

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

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

return result >= 0;

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

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: дополнение two, поразрядное дополнение до единицы и даже знак/величина. Все, о чем мы заботимся, - то, что любое положительное целое число со знаком (очищенный MSB) соответствует ниже чего-либо набору MSB.

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