Fastest / fastest algorithm for least positive number

Question

Simple question. In C ++, what is the easiest way to get which of the two numbers (u0 and u1) is the smallest positive number? (which is still effective)

Every way I'm trying to do includes big if statements or complex conditional statements.

Thanks Dan

Here is a simple example:

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

Answer 1

I prefer clarity in compactness:

 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 2

If the values ​​are presented in double additions, then

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

will work, since negative values ​​in a double complement are larger if considered unsigned than positive ones. As with Jeff's answer, this suggests that at least one of the values ​​is positive.

 return result >= 0; 

Answer 3

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

EDIT: Thought it wasn't so interesting, so I deleted it. But on a second thought, just leave it here for fun :) This can be seen as a dump version of Doug's answer :)

Answer 4

Could get me changed, but only for kicks, here is the result without any comparisons, because comparisons are for whimps .:-)

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

Note: Fails (u + v)> max_int. At least one number must be positive for the correct return code. Also compliant for politician decision :)

Answer 5

Here's a quick fix in C using the twiddling bit to find min(x, y) . This is a modified version of the @Doug Currie answer and inspired by the answer to Find a question about the minimum positive value :

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

Example:

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

Output:

 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 6

I suggest you reorganize this function into simpler functions. In addition, it allows your compiler to better apply the expected input.

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

This works in all three declared integer representations permitted by ISO C: two additions, one addition, and even a sign / value. All we care about is that any signed positive integer (MSB cleared) is compared below with the MSB set.

It really compiles for really nice code with clang for x86, as you can see in Godbolt Compiler Browser . gcc 5.3 unfortunately does a much worse job .

Answer 7

This will handle all possible inputs upon your request.

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

Thus, the signature that you supply allows you to get sneaky errors, as it is easy to ignore the return value of this function or not even remember that there is a return value that needs to be checked to find out if the result is correct.

You may prefer one of these alternatives, which makes it harder to lose sight of the need to verify the success result:

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

or

 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

tons of answers here ignore the fact that zero is not positive :)

with cunning casting and edge:

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

less cute:

 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 9

Three lines using (abuse?) Ternary operator

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

I do not know about efficiency or what to do if both u1 and u2 are negative. I decided to return NULL (which should be checked on the caller); returning a pointer to static -1 may be more useful.

Edited to reflect changes to the original question :)

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

Answer 10

Hacking using the "magic constant" -1:

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

This does not make assumptions about positive numbers.

Answer 11

Pseudocode because I don't have a compiler:

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

It is compact without many if statements, but relies on the ternary operator "?:", Which is simply compact if, then, else. "(true?" yes ":" no ")" returns "yes", "(false?" yes ":" no ") returns" no ".

In the normal switch statement, after each case, you must have break; to exit the switch. In this case, we have a return statement, so we exit the entire function.

Answer 12

With all due respect, your problem may be that the English phrase used to describe the problem really hides some complexity (or at least some unresolved issues). In my experience, this is a common source of errors and / or unfulfilled expectations in the "real world." Here are some of the issues that I have observed:

• Some programmers use a naming convention in which the leading u implies unsigned, but you do not explicitly indicate “numbers” are not signed or signed (or, for that matter, even have to be integers!)

• I suspect that all of us who read it have suggested that if one argument is positive and the other is not, then the value of the (only) positive argument is the correct answer, but this is not explicitly stated.

• The description also does not define the required behavior if both values ​​are non-positive.

• Finally, some of the answers suggested before this post seem to imply that the respondent thought (by mistake) that 0 is positive! more specific requirements can help prevent a misunderstanding (or make it clear that the question of zero was not fully thought out when the requirement was written).

I am not trying to be overly critical; I just suggest that a more accurately written requirement is likely to help, and probably also makes it clear whether there is really any kind of complexity that bothers you in the implementation, in the nature of the problem.

Answer 13

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

You are looking for the smallest positive , it is reasonable to accept positive values ​​only in this case. You do not need to catch the problem with negative values ​​in your function, you must solve it at an earlier point in the caller's function. For the same reason, I left the Boolean oit.

The prerequisite is that they are not equal, you should use it as follows:

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

You can enter const if you want to prevent changes or links if you want to change the result. Under normal conditions, the computer will optimize and even embed the function.

Answer 14

There is no intelligence, reasonable clarity, it works for int and floats:

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

• Note that 0 (zero) is not a positive number.
• The OP requests the processing of numbers (I interpret this as ints and floats).
• Only dereference result pointer, if there is a positive result (performance)
• Check only a and b for positivity once (performance - not sure if such a test is expensive?)

Please note that the accepted answer (by tvanfosson) is incorrect . It fails if a is positive and b is negative (saying "not one is positive"). (This is the only reason I am adding a separate answer - I do not have enough reputation to add comments.)

Answer 15

My idea is based on the use of min and max. And classified the result into three cases, where

• min <= 0 and max <= 0
• min <= 0 and max> 0
• min> 0 and max> 0

Best of all, it doesn't look too complicated. The code:

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

Answer 16

After my first message was rejected, let me assume that you are optimizing the problem prematurely, and you should not worry about having many if statements. The code you write naturally requires several if statements, and whether they are expressed using the triple if (A? B: C) or classic if statement, the execution time is the same, the compiler will optimize almost all the code sent to almost the same logic .

Respect your readability and the reliability of your code, rather than trying to outsmart your future or anyone else reading the code. Each posted solution is O (1) from what I can say, that is, each individual solution will make a minor contribution to the performance of your code.

I would suggest that this post be flagged as "premature optimization", the poster is not looking for elegant code.