Thread: Find if number x is less than y without comparison operator.

  1. #1
    Registered User
    Join Date
    May 2021
    Posts
    17

    Find if number x is less than y without less than operator.

    This implementation is correct but inefficient.

    Code:
    static int lessThan(int number1, int number2) {
        int i = 1;
        while (number1 && number2) {
            number1 = number1 - 1;
            number2 = number2 - 1;
        }
        if (number1 == 0) {
            i = 0;
        }
        return i;
    }
    Last edited by ZTik; 05-07-2021 at 08:35 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,629
    So what's == if it's not a comparison operator?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2021
    Posts
    17
    My mistake, I meant greater-less than operator.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,313
    As conjectured in your other topic:
    Quote Originally Posted by Salem
    Seems like one of those pointless exercises like add two numbers without using +

    It seems the OP is lumbered with a tutor who thinks magic tricks is how you teach programming.
    Is this true?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Feb 2019
    Posts
    853
    Well... no '<' operator here (hehe)...
    Code:
    // Intel/AMD:
    int lessThan(int a, int b)
    {
      int r = 0;
    
      __asm__ __volatile__ (
        "cmpl %2,%1\n\t"
        "sets %b0"
        : "+r" (r) : "r" (a), "g" (b) );
    
      return r;
    }
    Another way to do it, purely in C, but also potentially inneficient (in comparison of using '<'):
    Code:
    #include <limits.h>
    
    int lessThan( int a, int b )
    {
      unsigned int r = a - b;
      return ( r >> (sizeof(int) * CHAR_BIT - 1) );
    }
    And I agree with Salem... These kinds of exercises are pointless.
    Last edited by flp1969; 05-07-2021 at 10:11 AM.

  6. #6
    Registered User
    Join Date
    Apr 2021
    Posts
    34
    I would suggest that you evaluate this question the same way a CPU evaluates this question: do a subtraction, and then look at the resulting number.

    A naive approach would be something like:

    Code:
         is_lt(a, b) // is a less than b?
    
            diff = b - a
    
            if diff is zero, a == b, so return false
            if diff is negative, a < b, so return false
            if diff is positive, b > a, so return true
    Tests:
    • is_lt(4, 0) ? diff = 0 - 4 == -4 -> negative, return false
    • is_lt(4, 4) ? diff = 4 - 4 == 0 -> zero, return false
    • is_lt(4, 5) ? diff = 5 - 4 == 1 -> positive, return true


    More tests:
    • is_lt(-100, -101) diff = -101 - -100 == -1 -> negative, return false (whoops!)
    • is_lt(100, -101) diff = -101 - 100 == -201 -> negative, return false (ok)
    • is_lt(-101, 100) diff = 100 - -101 == 201 -> positive ,return true


    So maybe if both are negative you have to switch things around?

    How can you test for zero? Seems easy.
    How can you test for negative/positive? It turns out this is super easy! Just look up how negative numbers are implemented in 2's-complement arithmetic and you're good to go!
    Last edited by aghast; 05-07-2021 at 12:35 PM. Reason: Formatting

  7. #7
    Registered User
    Join Date
    Feb 2019
    Posts
    853
    Ahhh... and this works very well:
    Code:
    int lessThan( int a, int b )
    { return (a - b) >> ( sizeof(int) * CHAR_BIT - 1 ); }
    Right shift with signed integers are "dependent of implementation", accondingly to ISO 9899, due to the fact that most processors implement "logical shifts" and "arithmetic shifts". If a logical shift is used the result will be 1 if a<b or 0, otherwise... if an arithmetic shift is used the result will be -1 if a < b, or 0, otherwise...

    Of couse, assuming two's complement are used and msb is the sign bit.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Weird behaviour with comparison operator
    By MedicineMan25 in forum C Programming
    Replies: 14
    Last Post: 12-06-2016, 01:04 PM
  2. Replies: 2
    Last Post: 11-11-2010, 02:27 PM
  3. floating point number comparison
    By lehe in forum C++ Programming
    Replies: 10
    Last Post: 05-18-2009, 07:11 PM
  4. floating point number comparison
    By stanlvw in forum C++ Programming
    Replies: 9
    Last Post: 04-27-2009, 01:44 PM
  5. Replies: 20
    Last Post: 08-21-2005, 07:49 PM

Tags for this Thread