按位运算符大于操作符的等效形式

Question

我正在编写一个函数，将判断两个整数中哪个较大。传递的参数是两个32位整数 2 。需要注意的是，此函数只能使用以下运算符：! ~ | & << >> ^（不能转换数据类型、不能使用其他数据类型，如有符号整数、*、/、-等）。

我的想法是用 ^ 将两个二进制数合并在一起，看哪些位置上的 1 值不相同。然后我想要做的是隔离最左边的 1 值，然后查看其中哪个数字包含该值。该值将是较大的那个数字。 （假设我们使用8位整数而不是32位） 如果传递的两个值是01011011 和 01101001 我将它们进行异或操作得到 00100010。 然后我想把它变成 00100000 ，即 01xxxxxx -> 01000000 然后用第一个数字进行 & 运算， 对结果进行 !! 操作并返回它。 如果是 1 ，则第一个数字较大。

有什么想法可以实现 01xxxxxx -> 01000000 或其他任何有帮助的方法吗？

注意：不能使用 if、while、for 等等。

- Gekctek

---

“你说的‘我想把它变成00100000，换句话说，01xxxxxx-> 01000000’是什么意思？” “你怎么从00100000得到01xxxxxx？” - Manlio

噢，拜托了... 你能用什么？你能用三元条件运算符吗？ - Luchian Grigore

不，没有三目运算符，它的目的是教我们如何基本地创建编程模块。 - Gekctek

我的意思是，你可以从01xxxxxx中获取01000000，其中x可以是0或1。 - Gekctek

在有符号整数中进行位运算是可疑的。C标准没有为负数指定任何特定的二进制表示。实际世界的表示几乎总是二进制补码，但一些编译器（例如GCC）利用未定义性来进行优化。由于符号显然可能很重要，这至少可能是一个问题。 - user180247

Answer 1

这是一个不带循环的版本，可以在O(lg b)操作内比较无符号整数。请注意，OP指出除了signed int之外没有其他数据类型，因此似乎本答案的前半部分不符合OP的规范。 （剧透版本在底部。）

请注意，我们要捕获的行为是当最高有效位的不匹配是a的1，b的0时。另一种思考方式是，如果a中的任何位大于b中的相应位，则意味着a大于b，只要在a中没有早于b中的相应位的位小。

为此，我们计算所有比b中的相应位更大的a位，并计算所有比b中的相应位小的a位。现在，我们想要屏蔽所有低于任何“小于”位的“大于”位，因此我们取所有“小于”位并将它们全部向右涂抹成一个掩码：最高有效位被设置到最低有效位，都是1。

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

结果值为0，如果a <= b，非零，如果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;
}

我会留给你解释它为什么有效的部分。

- Kaganar

Answer 2

将 001xxxxx 转换为 00100000，首先要执行以下操作：

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

（这是针对8位的，如果要扩展到32位，请在序列开始处添加8和16次移位。）

这样我们就得到了 00111111（有时也称为“位扩散”技术）。然后我们可以截取除第一个1位以外的所有位：

x ^= x >> 1;

留下了00100000。

- caf

---

有时我会称之为“位扩展”。通过快速搜索，我找不到任何关于该术语各个版本的可靠参考资料。 - Kaganar

@Kaganar：这就是我所知道的名字。尽管我无法回忆起我第一次听到它是什么时候。 - caf

Answer 3

使用逻辑运算符(&&, ||)和比较运算符(!=, ==)，需要使用无符号变量。

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

对于signed，可以扩展成以下内容：

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!

- Morpfh

---

逻辑运算符，比如 && 和 || 相当于 if/ else -- 特别地，它们被编译成完全相同的机器代码。因此，这不符合约束条件。(而且实际约束条件中列出的是运算符，这些并不在列表中。) - Greg Price

Answer 4

完全无分支(branchless)的Kaganar's smaller isGt function版本可能如下所示：

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

实际计算（在 x86 架构上使用 MSVC 2010 编译器）需要约 60 条指令，加上大约 10 次堆栈操作作为函数的前言/尾声。

- Philip Conrad

Answer 5

编辑：

好的，代码存在一些问题，但我进行了修正，下面的代码可以工作。

这个辅助函数比较数字的第 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
}

- Luchian Grigore

---

@Daniel 我打错字了，应该是 digit 而不是 n。 - Luchian Grigore

啊，我明白了，你只是想要 int digit = 1 << n 对吧？这个看起来会移动二次方的量。 - Daniel Lubarov

@Daniel，之前有几个问题，现在已经解决了 :) - Luchian Grigore

看起来不错 :-) 除了 n-1，你确定吗？如果您将最后一个有效位视为位1，那么这应该是正确的，但是您的示例代码似乎会下降到0。 - Daniel Lubarov

Answer 6

虽然我不想做别人的作业，但我还是忍不住了... :) 我相信其他人可以想出更紧凑的代码，但这是我的版本。它可以很好地工作，包括负数。

编辑：有一些错误需要修复。我会让原帖作者自己找到并解决。

    #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

Answer 7

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

将第一个数字加1，然后从可以表示的最大数字（全是1）中减去它。将该数字加到第二个数字上。如果溢出，则第一个数字小于第二个数字。

我不确定这是否正确。也就是说，您可能不需要加1，并且我不知道是否可以检查溢出（如果不能，则只需保留最后一位并在最后测试它是否为1）。

- Houshalter

Answer 8

编辑：底部的简单方法由于限制条件无效。我正在添加二分搜索函数和最终比较以检测更大的值：

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。

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

- vhallac

---

仅限于25个运算符且不允许使用循环。 - Gekctek

在这种情况下，您需要一个手动编写的二分查找（带有一些特殊处理）。更新答案时请附上源代码 - 描述起来需要太长时间。 :) - vhallac

没有if会使事情变得更加困难。如果能得到答案，我会更新回答。 - vhallac