25

I am working on a function that will essentially see which of two ints is larger. The parameters that are passed are 2 32-bit ints. The trick is the only operators allowed are ! ~ | & << >> ^ (no casting, other data types besides signed int, *, /, -, etc..).

My idea so far is to ^ the two binaries together to see all the positions of the 1 values that they don't share. What I want to do is then take that value and isolate the 1 farthest to the left. Then see of which of them has that value in it. That value then will be the larger. (Say we use 8-bit ints instead of 32-bit). If the two values passed were 01011011 and 01101001 I used ^ on them to get 00100010. I then want to make it 00100000 in other words 01xxxxxx -> 01000000 Then & it with the first number !! the result and return it. If it is 1, then the first # is larger.

Any thoughts on how to 01xxxxxx -> 01000000 or anything else to help?

Forgot to note: no ifs, whiles, fors etc...

Shubham
  • 2,847
  • 4
  • 24
  • 37
Gekctek
  • 1,161
  • 2
  • 12
  • 23
  • What do you mean by "I then want to make it 00100000 in other words 01xxxxxx-> 01000000"? How do you get 01xxxxxx from 00100000? – Manlio Apr 10 '12 at 21:21
  • Oh come on... what can you use? Can you use the ternary conditional? – Luchian Grigore Apr 10 '12 at 21:55
  • nope, no ternary, its to teach us how to essentially create the building blocks – Gekctek Apr 10 '12 at 22:14
  • I mean you get 01000000 from 01xxxxxx where x could be 0 or 1 – Gekctek Apr 10 '12 at 22:14
  • On the bright side, if you ever need to build an ALU for a CPU in an HDL, this question will actually have practical use :) – Earlz Apr 11 '12 at 03:22
  • Can you use logical `&&` and `||` ? – Morpfh Apr 11 '12 at 03:27
  • 1
    Doing bitwise stuff in signed integers is dubious. The C standard doesn't specify any particular binary representation for negative numbers. The real-world representation is almost always twos complement, but some compilers (e.g. GCC) exploit the undefinedness to do optimisations. As the sign can clearly be significant, this is at least potentially a problem. –  Apr 11 '12 at 09:48

8 Answers8

21

Here's a loop-free version which compares unsigned integers in O(lg b) operations where b is the word size of the machine. Note the OP states no other data types than signed int, so it seems likely the top part of this answer does not meet the OP's specifications. (Spoiler version as at the bottom.)

Note that the behavior we want to capture is when the most significant bit mismatch is 1 for a and 0 for b. Another way of thinking about this is any bit in a being larger than the corresponding bit in b means a is greater than b, so long as there wasn't an earlier bit in a that was less than the corresponding bit in b.

To that end, we compute all the bits in a greater than the corresponding bits in b, and likewise compute all the bits in a less than the corresponding bits in b. We now want to mask out all the 'greater than' bits that are below any 'less than' bits, so we take all the 'less than' bits and smear them all to the right making a mask: the most significant bit set all the way down to the least significant bit are now 1.

Now all we have to do is remove the 'greater than' bits set by using simple bit masking logic.

The resulting value is 0 if a <= b and nonzero if a > b. If we want it to be 1 in the latter case we can do a similar smearing trick and just take a look at the least significant bit.

#include <stdio.h>

// Works for unsigned ints.
// Scroll down to the "actual algorithm" to see the interesting code.

// Utility function for displaying binary representation of an unsigned integer
void printBin(unsigned int x) {
    for (int i = 31; i >= 0; i--) printf("%i", (x >> i) & 1);
    printf("\n");
}
// Utility function to print out a separator
void printSep() {
    for (int i = 31; i>= 0; i--) printf("-");
    printf("\n");
}

int main()
{
    while (1)
    {
        unsigned int a, b;

        printf("Enter two unsigned integers separated by spaces: ");
        scanf("%u %u", &a, &b);
        getchar();

        printBin(a);
        printBin(b);
        printSep();

            /************ The actual algorithm starts here ************/

        // These are all the bits in a that are less than their corresponding bits in b.
        unsigned int ltb = ~a & b;

        // These are all the bits in a that are greater than their corresponding bits in b.
        unsigned int gtb = a & ~b;

        ltb |= ltb >> 1;
        ltb |= ltb >> 2;
        ltb |= ltb >> 4;
        ltb |= ltb >> 8;
        ltb |= ltb >> 16;

        // Nonzero if a > b
        // Zero if a <= b
        unsigned int isGt = gtb & ~ltb;

        // If you want to make this exactly '1' when nonzero do this part:
        isGt |= isGt >> 1;
        isGt |= isGt >> 2;
        isGt |= isGt >> 4;
        isGt |= isGt >> 8;
        isGt |= isGt >> 16;
        isGt &= 1;

            /************ The actual algorithm ends here ************/

        // Print out the results.
        printBin(ltb); // Debug info
        printBin(gtb); // Debug info
        printSep();
        printBin(isGt); // The actual result
    }
}

Note: This should work for signed integers as well if you flip the top bit on both of the inputs, e.g. a ^= 0x80000000.

Spoiler

If you want an answer that meets all of the requirements (including 25 operators or less):

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

    diff &= ~(diff >> 1) | 0x80000000;
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

    return !!diff;
}

I'll leave explaining why it works up to you.

Kaganar
  • 6,540
  • 2
  • 26
  • 59
6

To convert 001xxxxx to 00100000, you first execute:

x |= x >> 4;
x |= x >> 2;
x |= x >> 1;

(this is for 8 bits; to extend it to 32, add shifts by 8 and 16 at the start of the sequence).

This leaves us with 00111111 (this technique is sometimes called "bit-smearing"). We can then chop off all but the first 1 bit:

x ^= x >> 1;

leaving us with 00100000.

caf
  • 233,326
  • 40
  • 323
  • 462
  • Well, sometimes called "bit-smearing" by me. I can't find any solid references to various versions of the term via some fast Googling. – Kaganar Apr 11 '12 at 13:34
  • @Kaganar: That's the name by which I've known it too. I can't recall when I first heard it, though. – caf Apr 12 '12 at 02:10
5

An unsigned variant given that one can use logical (&&, ||) and comparison (!=, ==).

int u_isgt(unsigned int a, unsigned int b)
{
    return a != b && (    /* If a == b then a !> b and a !< b.             */
               b == 0 ||  /* Else if b == 0 a has to be > b (as a != 0).   */
               (a / b)    /* Else divide; integer division always truncate */
           );             /*              towards zero. Giving 0 if a < b. */
}

!= and == can easily be eliminated., i.e.:

int u_isgt(unsigned int a, unsigned int b)
{
    return a ^ b && (
               !(b ^ 0) ||
               (a / b)
           );
}

For signed one could then expand to something like:

int isgt(int a, int b)
{
    return
    (a != b) &&
    (
        (!(0x80000000 & a) && 0x80000000 & b) ||  /* if a >= 0 && b < 0  */
        (!(0x80000000 & a) && b == 0) ||
        /* Two more lines, can add them if you like, but as it is homework
         * I'll leave it up to you to decide. 
         * Hint: check on "both negative" and "both not negative". */
    )
    ;
}

Can be more compact / eliminate ops. (at least one) but put it like this for clarity.

Instead of 0x80000000 one could say ie:

#include <limits.h>
static const int INT_NEG = (1 << ((sizeof(int) * CHAR_BIT) - 1));

Using this to test:

void test_isgt(int a, int b)
{
    fprintf(stdout,
        "%11d > %11d = %d : %d %s\n",
        a, b,
        isgt(a, b), (a > b),
        isgt(a, b) != (a>b) ? "BAD!" : "OK!");
}

Result:

         33 >           0 = 1 : 1 OK!
        -33 >           0 = 0 : 0 OK!
          0 >          33 = 0 : 0 OK!
          0 >         -33 = 1 : 1 OK!
          0 >           0 = 0 : 0 OK!
         33 >          33 = 0 : 0 OK!
        -33 >         -33 = 0 : 0 OK!
         -5 >         -33 = 1 : 1 OK!
        -33 >          -5 = 0 : 0 OK!
-2147483647 >  2147483647 = 0 : 0 OK!
 2147483647 > -2147483647 = 1 : 1 OK!
 2147483647 >  2147483647 = 0 : 0 OK!
 2147483647 >           0 = 1 : 1 OK!
          0 >  2147483647 = 0 : 0 OK!
Morpfh
  • 4,033
  • 18
  • 26
  • 2
    Logical operators like `&&` and `||` are equivalent to `if`/`else` -- in particular, they get compiled to exactly the same machine code. So this doesn't meet the constraints. (Also the actual statement of the constraints lists operators and these aren't on the list.) – Greg Price Nov 08 '13 at 08:03
2

A fully branchless version of Kaganar's smaller isGt function might look like so:

int isGt(int a, int b)
{
    int diff = a ^ b;
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;

    //1+ on GT, 0 otherwise.
    diff &= ~(diff >> 1) | 0x80000000;
    diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);

    //flatten back to range of 0 or 1.
    diff |= diff >> 1;
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff &= 1;

    return diff;
}

This clocks in at around 60 instructions for the actual computation (MSVC 2010 compiler, on an x86 arch), plus an extra 10 stack ops or so for the function's prolog/epilog.

Community
  • 1
  • 1
Philip Conrad
  • 1,451
  • 1
  • 13
  • 22
0

EDIT:

Okay, there were some issues with the code, but I revised it and the following works.

This auxiliary function compares the numbers' n'th significant digit:

int compare ( int a, int b, int n )
{
    int digit = (0x1 << n-1);
    if ( (a & digit) && (b & digit) )
       return 0; //the digit is the same

    if ( (a & digit) && !(b & digit) )
       return 1; //a is greater than b

    if ( !(a & digit) && (b & digit) )
       return -1; //b is greater than a
}

The following should recursively return the larger number:

int larger ( int a, int b )
{
    for ( int i = 8*sizeof(a) - 1 ; i >= 0 ; i-- )
    {
       if ( int k = compare ( a, b, i ) )
       {
           return (k == 1) ? a : b;
       }
    }
    return 0; //equal
}
Community
  • 1
  • 1
Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
0

As much as I don't want to do someone else's homework I couldn't resist this one.. :) I am sure others can think of a more compact one..but here is mine..works well, including negative numbers..

Edit: there are couple of bugs though. I will leave it to the OP to find it and fix it.

    #include<unistd.h>
    #include<stdio.h>
    int a, b, i, ma, mb, a_neg, b_neg, stop;

    int flipnum(int *num, int *is_neg) {
        *num = ~(*num) + 1;
        *is_neg = 1;

        return 0;
    }

    int print_num1() {
        return ((a_neg && printf("bigger number %d\n", mb)) ||
             printf("bigger number %d\n", ma));
    }

    int print_num2() {
        return ((b_neg && printf("bigger number %d\n", ma)) ||
             printf("bigger number %d\n", mb));
    }

    int check_num1(int j) {
        return ((a & j) && print_num1());
    }

    int check_num2(int j) {
        return ((b & j) && print_num2());
    }

    int recursive_check (int j) {
        ((a & j) ^ (b & j)) && (check_num1(j) || check_num2(j))  && (stop = 1, j = 0);

        return(!stop && (j = j >> 1) && recursive_check(j));
    }

    int main() {
        int j;
        scanf("%d%d", &a, &b);
        ma = a; mb = b;

        i = (sizeof (int) * 8) - 1;
        j = 1 << i;

        ((a & j) && flipnum(&a, &a_neg));

        ((b & j) && flipnum(&b, &b_neg));

        j = 1 << (i - 1);

        recursive_check(j);

        (!stop && printf("numbers are same..\n"));
    }
Manohar
  • 3,865
  • 11
  • 41
  • 56
0

I think I have a solution with 3 operations:

Add one to the first number, the subtract it from the largest possible number you can represent (all 1's). Add that number to the second number. If it it overflows, then the first number is less than the second.

I'm not 100% sure if this is correct. That is you might not need to add 1, and I don't know if it's possible to check for overflow (if not then just reserve the last bit and test if it's 1 at the end.)

Houshalter
  • 2,508
  • 1
  • 18
  • 20
-1

EDIT: The constraints make the simple approach at the bottom invalid. I am adding the binary search function and the final comparison to detect the greater value:

unsigned long greater(unsigned long a, unsigned long b) {
    unsigned long x = a;
    unsigned long y = b;
    unsigned long t = a ^ b;
    if (t & 0xFFFF0000) {
        x >>= 16;
        y >>= 16;
        t >>= 16;
    }
    if (t & 0xFF00) {
        x >>= 8;
        y >>= 8;
        t >>= 8;
    }
    if (t & 0xf0) {
        x >>= 4;
        y >>= 4;
        t >>= 4;
    }
    if ( t & 0xc) {
        x >>= 2;
        y >>= 2;
        t >>= 2;
    }
    if ( t & 0x2) {
        x >>= 1;
        y >>= 1;
        t >>= 1;
    }
    return (x & 1) ? a : b;
}

The idea is to start off with the most significant half of the word we are interested in and see if there are any set bits in there. If there are, then we don't need the least significant half, so we shift the unwanted bits away. If not, we do nothing (the half is zero anyway, so it won't get in the way). Since we cannot keep track of the shifted amount (it would require addition), we also shift the original values so that we can do the final and to determine the larger number. We repeat this process with half the size of the previous mask until we collapse the interesting bits into bit position 0.

I didn't add the equal case in here on purpose.

Old answer:

The simplest method is probably the best for a homework. Once you've got the mismatching bit value, you start off with another mask at 0x80000000 (or whatever suitable max bit position for your word size), and keep right shifting this until you hit a bit that is set in your mismatch value. If your right shift ends up with 0, then the mismatch value is 0.

I assume you already know the final step required to determine the larger number.

vhallac
  • 13,301
  • 3
  • 25
  • 36