按位运算等效于大于运算符

Question

我正在研究一个函数,它基本上可以看到两个整数中的哪一个更大.传递的参数是232位整数.诀窍是允许的唯一运算符! ~ | & << >> ^(没有转换,除了signed int,*,/, - 等其他数据类型).

到目前为止,我的想法是^将两个二进制文件放在一起,以查看1它们不共享的值的所有位置.我想要做的就是取这个值并将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的相应位大于任何位,只要没有较早的位小于相应的位.babab

为此,我们计算a大于相应位的b所有位,同样计算所有位a小于相应位的位b.我们现在想要掩盖低于任何'小于'位的所有'大于'位,所以我们取所有'小于'位并将它们全部涂抹到右边制作一个掩码:最重要的位设置全部现在是最重要的一点1.

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

结果值为0,如果为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;
}

我会留下解释为什么它适合你.

Answer 2

一个无符号变量,可以使用逻辑(&&,||)和比较(!=,==).

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一个可以说ie:

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

Answer 3

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

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

（这是8位；将其扩展到32位，在序列的开始处增加8和16的移位）。

这给我们留下了00111111（这种技术有时称为“位拖尾”）。然后，我们可以切掉除前1个位之外的所有位：

x ^= x >> 1;

与我们在一起00100000。