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

查看：183
本文介绍了按位运算相当于大于运营商的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我的工作，将主要看这两个整数的更大的功能。所传递的参数是2的32位整数。诀窍是唯一的运营商允许的！ 〜| ＆安培; ＆LT;＆LT; >> ^（无铸造，除了符号整数其他数据类型，*，/， - ，等..）。

我的想法到目前为止是^两个二进制文件一起看到，他们不共享1值的所有位置。我想要做的就是再取该值和隔离1最远到左侧。然后看看哪些有它该值。然后该值将越大。
（说我们使用的8位整数，而不是32位）
如果通过这两个值分别为01011011和01101001
我用^他们获得00100010。
然后，我希望把它00100000换句话说01xxxxxx-> 01000000
然后＆功放;它与第一个数字
！结果并将其返回。
如果是1，则第一＃较大

如何01xxxxxx-> 01000000或其他任何东西，以帮助有什么想法？

忘了注意：没有如果，田地，维权等...


<格CLASS =h2_lin>解决方案

下面是其无符号整数在O（LG B）进行比较运算，其中b是机器字长无环路的版本。注意OP状态没有其他数据类型符号int ，所以它很可能这个答案的上半部分不符合OP的规格。 （尾翼版本作为在底部。）

请注意，我们要捕捉行为是当最显著位不匹配 1 为 A 和 0 为 b 。考虑这个的另一种方式是在任何位 A 比在 B 办法<$ C $对应的有点大C> A 比大于b ，所以只要不是在更早位 A 这是不到相应的位在 b 。

为此，我们计算在所有位比相应的位B A 更大，同样在计算 b 所有位比相应的位少。我们现在要屏蔽掉所有的'大于'是以下的任何小于的位，所以我们把所有的小于位，并在所有的涂抹到右侧使得一个屏蔽位：最显著位设置的所有一直到最低显著位的方式，现在 1 。

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

结果值是0，如果 A＆LT; = B 和非零如果 A＆GT; b 。如果我们希望它是 1 在后一种情况下，我们可以做一个类似的伎俩抹黑，只是来看看的至少显著位。

 的#include＆LT;＆stdio.h中GT;// Works的无符号整数。
//向下滚动到实际的算法看到有趣code。//用于显示无符号整数的二进制重新presentation效用函数
无效printBin（unsigned int类型X）{
    对于（INT I = 31; I＆GT; = 0;我 - ）的printf（％i的，（X GT;＆GT;我）及1）;
    的printf（\\ n）;
}
//效用函数打印出一个分离器
无效printSep（）{
    对于（INT I = 31; I＆GT; = 0;我 - ）的printf（ - ）;
    的printf（\\ n）;
}诠释的main（）
{
    而（1）
    {
        unsigned int类型A，B;        的printf（请输入空格分隔的两个无符号整数：）;
        scanf函数（％U％U，＆安培;一，和b）;
        的getchar（）;        printBin（一）;
        printBin（二）;
        printSep（）;            / ************实际的算法从这里开始************ /        //这些都是在该小于b中的相应位的位。
        unsigned int类型LTB =〜A和b：        //这些都是在那些比b中的相应位更大的位。
        unsigned int类型GTB = A和一B;        LTB | = LTB＆GT;＆GT; 1;
        LTB | = LTB＆GT;＆GT; 2;
        LTB | = LTB＆GT;＆GT; 4;
        LTB | = LTB＆GT;＆GT; 8;
        LTB | = LTB＆GT;＆GT; 16;        //非零如果＆GT; b
        //零如果＆LT; = B
        unsigned int类型isGt = GTB＆安培; 〜LTB;        //如果你想使这个正是1时，非零这样做的部分：
        isGt | = isGt＆GT;＆GT; 1;
        isGt | = isGt＆GT;＆GT; 2;
        isGt | = isGt＆GT;＆GT; 4;
        isGt | = isGt＆GT;＆GT; 8;
        isGt | = isGt＆GT;＆GT; 16;
        isGt＆放大器; = 1;            / ************实际的算法在这里结束************ /        //打印出结果。
        printBin（LTB）; //调试信息
        printBin（GTB）; //调试信息
        printSep（）;
        printBin（isGt）; //实际结果
    }
}

请注意：这应该有符号整数工作，以及如果你翻车上的两个的的输入，例如最高位 A ^ = 0x80000000的。

扰流

如果你想满足所有的需求（包括25家运营商或更少）的答案是：

  INT isGt（int类型的，INT B）
{
    INT差异= A ^ B;
    差异| = DIFF＆GT;＆GT; 1;
    差异| = DIFF＆GT;＆GT; 2;
    差异| = DIFF＆GT;＆GT; 4;
    差异| = DIFF＆GT;＆GT; 8;
    差异| = DIFF＆GT;＆GT; 16;    DIFF＆安培; =〜（DIFF＆GT;＆GT; 1）| 0x80000000的;
    DIFF＆安培; =（A ^为0x80000000）及（二^ 0x7FFFFFFF的）;    返回!!差异;
}

我会离开，解释为什么它的作品给你。

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

解决方案

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

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.

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.

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("\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
    }
}

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

Spoiler

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屋！

查看全文
相关文章
开发方法最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆