相当于大于运算符的按位运算 [英] Bitwise operations equivalent of greater than operator

问题描述

我正在研究一个函数，该函数基本上可以查看两个整数中的哪一个更大.传递的参数是 2 32 位整数.诀窍是唯一允许的运算符是 !~ |&<<>>^(无强制转换，除有符号整数、*、/、- 等之外的其他数据类型.).

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

到目前为止，我的想法是将两个二进制文件 ^ 放在一起，以查看它们不共享的 1 值的所有位置.然后我想要做的是取那个值并将 1 隔离到最左边.然后看看其中哪一个有这个价值.那么该值将更大.(假设我们使用 8 位整数而不是 32 位).如果传递的两个值是 01011011 和 01101001我在它们上使用了 ^ 来获取 00100010.然后我想让它 00100000 换句话说 01xxxxxx ->01000000然后 & 它与第一个数字!! 结果并返回.如果是1，那么第一个#比较大.

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.

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

Any thoughts on how to 01xxxxxx -> 01000000 or anything else to help?

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

Forgot to note: no ifs, whiles, fors etc...

推荐答案

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

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

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

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.

为此，我们计算 a 中的所有位大于 b 中的相应位，并同样计算 a 中的所有位> 小于 b 中的相应位.我们现在要屏蔽掉所有低于任何小于"位的大于"位，因此我们取出所有小于"位并将它们全部涂抹在右侧，形成一个掩码:最高有效位全部设置现在到最低有效位的路径是 1.

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.

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

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

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

Note: This should work for signed integers as well if you flip the top bit on both of the inputs, e.g. a ^= 0x80000000.

如果您想要一个满足所有要求的答案(包括 25 名或更少):

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.

这篇关于相当于大于运算符的按位运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！