c - 按位运算相当于大于运算符

Question

我正在开发一个函数，它基本上可以查看两个整数中哪个更大。传递的参数是2 32 位整数。诀窍是唯一允许的运算符是 ! ~ | & << >> ^ (没有转换，除了 signed int、*、/、- 等之外的其他数据类型)。

到目前为止我的想法是^两个二进制文件一起查看 1 的所有位置他们不分享的值(value)观。然后我想做的是获取该值并隔离 1最左边。然后看看其中哪些具有该值。该值将更大。(假设我们使用 8 位整数而不是 32 位)。如果传递的两个值是 01011011和 01101001我用了^在他们身上得到00100010 .然后我想把它做成00100000换句话说 01xxxxxx -> 01000000然后 &它与第一个数字 !!结果并返回。如果是1 , 然后是第一个 #更大。

关于如何 01xxxxxx -> 01000000 的任何想法或其他任何帮助？

忘记注意:没有 ifs、whiles、fors 等......

Answer 1

这是一个无循环版本，它在 O(lg b) 操作中比较无符号整数，其中 b 是机器的字长。请注意，OP 声明除 signed int 外没有其他数据类型。 ，所以这个答案的顶部似乎不符合 OP 的规范。 (扰流板版本在底部。)

请注意，我们要捕获的行为是最高有效位不匹配为 1 时的行为对于 a和 0对于 b .另一种思考方式是 a 中的任何一点。大于 b 中的相应位表示 a大于 b , 只要 a 中没有更早的位小于 b 中的相应位.

为此，我们计算了 a 中的所有位大于b中的相应位, 并同样计算 a 中的所有位小于b中的相应位.我们现在想要屏蔽所有低于任何“小于”位的“大于”位，因此我们采用所有“小于”位并将它们全部涂抹到右边制作掩码:最高有效位全部设置现在下降到最低有效位的方式是1 .

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

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

我会解释为什么它适合你。