23

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

4

8 回答 8

20

这是一个无循环版本，它比较 O(lg b) 操作中的无符号整数，其中 b 是机器的字长。请注意，OP 声明除 之外没有其他数据类型signed int，因此该答案的上半部分似乎不符合 OP 的规范。（剧透版本在底部。）

请注意，我们要捕获的行为是最重要的位不匹配时1fora和0for b。另一种思考方式是任何位a大于 中的相应位b均值a大于b，只要没有较早的位a小于 中的相应位b。

为此，我们计算a大于 中相应位的b所有位，同样计算a小于 中相应位的所有位b。我们现在想要屏蔽掉所有低于任何“小于”位的“大于”位，因此我们取出所有“小于”位并将它们全部涂抹到右侧，形成一个掩码：最高有效位全部设置下降到最低有效位的方法是现在1。

现在我们要做的就是使用简单的位掩码逻辑删除“大于”位设置。

结果值为 0 ifa <= b和非零 if a > b。如果我们希望它1在后一种情况下，我们可以做一个类似的涂抹技巧，只看一下最低有效位。

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

注意：如果您翻转两个输入的最高位，这也适用于有符号整数，例如a ^= 0x80000000.

剧透

如果您想要一个满足所有要求的答案（包括 25 个或更少的运算符）：

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

我会解释为什么它对你有用。

于 2012-04-10T22:07:06.227 回答
6

要转换001xxxxx为00100000，首先执行：

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

（这是 8 位；要将其扩展到 32，请在序列的开头添加 8 和 16 的移位）。

这给我们留下了00111111（这种技术有时被称为“位涂抹”）。然后我们可以砍掉除前 1 位之外的所有内容：

x ^= x >> 1;

留给我们00100000。

于 2012-04-11T07:30:18.697 回答
5

一种无符号变体，可以使用逻辑（&&，||）和比较（！=，==）。

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

!=并且==很容易被淘汰，即：

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

对于已签名的，然后可以扩展为：

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

可以更紧凑/消除操作。（至少一个），但为了清楚起见，这样写。

而不是0x80000000一个人可以说，即：

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

使用它来测试：

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

结果：

         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!
于 2012-04-10T23:49:06.423 回答
2

Kaganar 较小的 isGt 函数的完全无分支版本可能如下所示：

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

这大约有 60 条指令用于实际计算（MSVC 2010 编译器，在 x86 架构上），另外还有大约 10 个堆栈操作用于函数的序言/结语。

于 2013-01-06T07:19:55.667 回答
0

尽管我不想做别人的作业，但我无法抗拒这个.. :) 我相信其他人可以想到一个更紧凑的..但这是我的.. 效果很好，包括负数。 .

编辑：虽然有几个错误。我将把它留给 OP 来查找并修复它。

    #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"));
    }
于 2012-04-11T06:55:31.710 回答
0

编辑：

好的，代码存在一些问题，但我修改了它并且以下工作。

此辅助函数比较数字的第 n 个有效数字：

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
}

以下应递归返回较大的数字：

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
}
于 2012-04-10T21:39:35.813 回答
0

我想我有一个包含 3 个操作的解决方案：

在第一个数字上加一个，从您可以表示的最大可能数字中减去它（全为 1）。将该数字添加到第二个数字。如果它溢出，那么第一个数字小于第二个。

我不是 100% 确定这是否正确。那就是你可能不需要加 1，而且我不知道是否可以检查溢出（如果没有，那么只需保留最后一位并测试它最后是否为 1。）

于 2015-05-11T05:23:32.600 回答
-1

编辑：约束使底部的简单方法无效。我正在添加二进制搜索功能和最终比较以检测更大的值：

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

这个想法是从我们感兴趣的单词的最重要的一半开始，看看那里是否有任何设置位。如果有，那么我们不需要最低有效的一半，因此我们将不需要的位移开。如果没有，我们什么也不做（反正一半是零，所以不会妨碍）。由于我们无法跟踪移动的数量（它需要添加），我们还移动了原始值，以便我们可以进行最终and确定更大的数字。我们用前一个掩码的一半大小重复这个过程，直到我们将感兴趣的位折叠到位位置 0。

我没有故意在这里添加相同的大小写。

老答案：

最简单的方法可能是最好的家庭作业。一旦你得到了不匹配的位值，你就从 0x80000000 的另一个掩码开始（或任何适合你的字大小的最大位位置），并继续向右移动它，直到你碰到在你的不匹配值中设置的位。如果您的右移以 0 结束，则不匹配值为 0。

我假设您已经知道确定较大数字所需的最后一步。

于 2012-04-10T21:41:33.937 回答