c - Bitwise operations equivalent of greater than operator

Question

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...

Answer 1

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("
");
}
// Utility function to print out a separator
void printSep() {
    for (int i = 31; i>= 0; i--) printf("-");
    printf("
");
}

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.