如何使用按位运算符比较两个无符号整数？

Question

如何在不使用任何算术运算符或比较运算符的情况下使用按位运算符来查看两个无符号整数中较大者？

Answer 1

如果您要处理数字的十进制表示，您会说位数最多的是较大的。

如果两个数字的位数相同怎么办？好吧，你依次比较每个数字，从最重要的开始。

在十进制中，这很难满足您的要求。但是在二进制中，我们可以执行简单的真值测试。因此，这里可以使用这种方法。

+---+---+---+---+       +---+---+---+---+
| 0 | 1 | 1 | 0 |  6    | 0 | 1 | 1 | 0 |  6
+---+---+---+---+       +---+---+---+---+
  →   ↑            ↑      →   →   ↑        ↑
+---+---+---+---+       +---+---+---+---+
| 0 | 0 | 1 | 0 |  2    | 0 | 1 | 0 | 0 |  4
+---+---+---+---+       +---+---+---+---+

因此，这适用于相同大小的无符号整数：

隔离每个数字的最高有效位。
如果它们不同，则设置的位更大。
如果不是，重复下一个最高有效位。

有一个更简单的解决方案，涉及查找两个输入数字的异或。

Answer 2

让我们考虑两个整数 4 (0100) 和 3 (0011)。我们需要生成区分两个整数的最大子位系列，例如上面是 0100（因为第三位不同），那么我们可以通过位与运算简单地知道哪个更大：

0100 & 0100 = 0100 > 0  
0011 & 0100 = 0

代码如下：

#include <stdio.h>
int main()
{
  int a, b;

  printf("Enter two numbers\n");
  scanf("%d%d", &a, &b);

  int diff = a ^ b;
  if (diff)  //true means both are not equal
  {
    diff = diff | (diff >> 1);
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff ^= diff >> 1;

    int res = (a & diff) ? 1 : 0;

    if (res)
        printf("%d greater than %d", a, b);
    else
        printf("%d greater than %d", b, a);
   }

  else //both equal
  {
    printf("Both are equal\n");
    return 0;
  }


  return 0;
}

Answer 3

在循环中使用 XOR（异或）和 SHL（左移）即可。

XOR（在 C 中：^）是 [在低级别 H/W] 中测试相等性的正常方法。这是一个基本的逻辑门。

如果两个数的异或为零，则它们相等。

但是，两个数字的 XOR 会产生一个位掩码，如果两个数字中的任何位不同，则对应的 XOR 位为 1（否则为 0）。

通过对 MSB 进行移位和屏蔽，我们可以找到最左边不同的位。

下面是一些说明这一点的代码。它有一个诊断测试，因此您可以验证您的功能：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int u32;

// RETURNS -1=a<b, 0=a==b, +1=a>b
int
cmpxor(u32 a,u32 b)
{
    u32 xor;
    u32 msb;
    int cmp = 0;

    // get a mask for the most signifcant bit
    msb = 1u << 31;

    // which bits are different
    xor = a ^ b;

    while (xor != 0) {
        // is the most significant bit different? if so, we are done
        if (xor & msb) {
            if (a & msb)
                cmp = 1;
            else
                cmp = -1;
            break;
        }

        xor <<= 1;
        a <<= 1;
    }

    return cmp;
}

int
cmpstd(u32 a,u32 b)
{
    int cmp = 0;

    if (a < b)
        cmp = -1;
    if (a > b)
        cmp = 1;

    return cmp;
}

int
main(int argc,char **argv)
{
    u32 a;
    u32 b;
    int cmpx;
    int cmps;
    u32 opt_L = 0;
    int code = 0;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'L':
            opt_L = (*cp != 0) ? atoll(cp) : 65536;
            break;
        }
    }

    if (opt_L == 0)
        opt_L = 1024;

    for (a = 0;  a < opt_L;  ++a) {
        for (b = 0;  b < opt_L;  ++b) {
            cmps = cmpstd(a,b);
            cmpx = cmpxor(a,b);
            if (cmps != cmpx) {
                printf("a=%8.8X b=%8.8X cmps=%d cmpx=%d\n",
                    a,b,cmps,cmpx);
                code = 1;
                break;
            }
        }
        if (code)
            break;
    }

    if (code == 0)
        printf("complete\n");

    return code;
}

更新：

我增强了诊断测试套件。而且，我添加了一些基准测试。

我还添加了两个源自 Krishna 答案的函数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef unsigned int u32;
typedef unsigned long long u64;

u32 opt_L = 0;
int opt_e;                              // number of errors to show per func
int opt_k;                              // don't stop next test if error
int opt_v;                              // show all values

// RETURNS -1=a<b, 0=a==b, +1=a>b
int
cmpxor(u32 a,u32 b)
{
    u32 xor;
    u32 msb;
    int cmp = 0;

    // get a mask for the most signifcant bit
    msb = 1u << 31;

    // which bits are different
    xor = a ^ b;

    while (xor != 0) {
        // is the most significant bit different? if so, we are done
        if (xor & msb) {
            if (a & msb)
                cmp = 1;
            else
                cmp = -1;
            break;
        }

        xor <<= 1;
        a <<= 1;
    }

    return cmp;
}

int
cmpstd(u32 a,u32 b)
{
    int cmp = 0;

    if (a < b)
        cmp = -1;
    if (a > b)
        cmp = 1;

    return cmp;
}

int
cmpki(int a, int b)
{
    int diff = a ^ b;
    int res;

    do {
        // Both are equal
        if (diff == 0) {
            res = 0;
            break;
        }

        diff = diff | (diff >> 1);
        diff |= diff >> 2;
        diff |= diff >> 4;
        diff |= diff >> 8;
        diff |= diff >> 16;
        diff ^= diff >> 1;

        // Conditonal operator is not a relational operator
        res = (a & diff) ? 1 : -1;
    } while (0);

    return res;
}

int
cmpku(u32 a, u32 b)
{
    u32 diff = a ^ b;
    int res;

    do {
        // Both are equal
        if (diff == 0) {
            res = 0;
            break;
        }

        diff = diff | (diff >> 1);
        diff |= diff >> 2;
        diff |= diff >> 4;
        diff |= diff >> 8;
        diff |= diff >> 16;
        diff ^= diff >> 1;

        // Conditonal operator is not a relational operator
        res = (a & diff) ? 1 : -1;
    } while (0);

    return res;
}

double tsczero;
double tscbeg;

double
tscget(void)
{
    struct timespec ts;
    double sec;

    clock_gettime(CLOCK_MONOTONIC,&ts);
    sec = ts.tv_nsec;
    sec /= 1e9;
    sec += ts.tv_sec;

    if (tsczero == 0)
        tsczero = sec;

    sec -= tsczero;

    return sec;
}

#define msgbeg(_fmt...) \
    do { \
        tscbeg = tscget(); \
        printf("%13.9f ",tscbeg); \
        printf(_fmt); \
        fflush(stdout); \
    } while (0)

void
msgend(void)
{

    double tscend = tscget();
    printf(" (ELAPSED: %.9f)\n",tscend - tscbeg);
}

typedef struct {
    int (*tst_fnc)(u32,u32);
    const char *tst_tag;
} tst_t;

tst_t tstlist[] = {
    { .tst_tag = "cmpxor", .tst_fnc = (void *) cmpxor },
    { .tst_tag = "cmpki", .tst_fnc = (void *) cmpki },
    { .tst_tag = "cmpku", .tst_fnc = (void *) cmpku },
    { .tst_tag = NULL }
};
int taglen;

int
dotest(tst_t *tst,u64 lo,u64 hi,u32 inc)
{
    u64 a;
    u64 b;
    int cmpx;
    int cmps;
    int badflg;
    int hangflg = 1;
    int ecnt = 0;

    msgbeg("dotest: %-*s %8.8llX/%8.8llX/%8.8X",taglen,tst->tst_tag,lo,hi,inc);

    for (a = lo;  a <= hi;  a += inc) {
        for (b = lo;  b <= hi;  b += inc) {
            cmps = cmpstd(a,b);
            cmpx = tst->tst_fnc(a,b);

            badflg = (cmps != cmpx);

            if (badflg || opt_v) {
                if (hangflg) {
                    hangflg = 0;
                    printf("\n");
                }

                printf("%-*s: %s a=%8.8llX b=%8.8llX cmps=%d cmpx=%d\n",
                    taglen,tst->tst_tag,badflg ? "FAIL" : "PASS",a,b,cmps,cmpx);

                if (badflg)
                    ++ecnt;

                if (opt_v)
                    continue;

                if (ecnt >= opt_e)
                    break;
            }
        }

        if (opt_v)
            continue;

        if (ecnt >= opt_e)
            break;
    }

    if (ecnt || opt_v) {
        if (hangflg)
            printf("\n");
        printf("%-*s: %d errors",taglen,tst->tst_tag,ecnt);
    }

    msgend();

    if (ecnt)
        ecnt = 1;

    return ecnt;
}

typedef struct {
    u32 rng_lo;
    u32 rng_hi;
    u32 rng_inc;
} rng_t;

rng_t rnglist[] = {
    { .rng_lo = 0x00000000, .rng_hi = 0x000000FF,   .rng_inc = 1 },
    { .rng_lo = 0x01000000, .rng_hi = 0xFFFFFFFF,   .rng_inc = 0x01000000 },
    { .rng_inc = 0 }
};

int
dorange(rng_t *rng)
{
    tst_t *tst;
    int code = 0;

    for (tst = tstlist;  tst->tst_tag != NULL;  ++tst) {
        code = dotest(tst,rng->rng_lo,rng->rng_hi,rng->rng_inc);
        if (! opt_k) {
            if (code)
                break;
        }
    }

    return code;
}

int
main(int argc,char **argv)
{
    int code = 0;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'e':
            opt_e = (*cp != 0) ? atoi(cp) : 0x7FFFFFFF;
            break;
        case 'k':
            opt_k = ! opt_k;
            break;
        case 'L':
            opt_L = (*cp != 0) ? atoll(cp) : 65536;
            break;
        case 'v':
            opt_v = ! opt_v;
            break;
        }
    }

    setlinebuf(stdout);

    if (opt_L == 0)
        opt_L = 256;

    if (opt_e == 0)
        opt_e = 1;
    if (opt_v)
        opt_e = 0x7FFFFFFF;

    // get max length of function name
    for (tst_t *tst = tstlist;  tst->tst_tag != NULL;  ++tst) {
        int curlen = strlen(tst->tst_tag);
        if (curlen > taglen)
            taglen = curlen;
    }

    // do all test ranges
    for (rng_t *rng = rnglist;  rng->rng_inc != 0;  ++rng) {
        code = dorange(rng);
        if (code)
            break;
    }

    if (code == 0)
        printf("complete\n");

    return code;
}

这是测试输出：

  0.000000000 dotest: cmpxor 00000000/000000FF/00000001 (ELAPSED: 0.001531766)
  0.001538215 dotest: cmpki  00000000/000000FF/00000001 (ELAPSED: 0.000467471)
  0.002008009 dotest: cmpku  00000000/000000FF/00000001 (ELAPSED: 0.000475924)
  0.002488059 dotest: cmpxor 01000000/FFFFFFFF/01000000 (ELAPSED: 0.000398438)
  0.002888709 dotest: cmpki  01000000/FFFFFFFF/01000000
cmpki : FAIL a=80000000 b=01000000 cmps=1 cmpx=-1
cmpki : 1 errors (ELAPSED: 0.000237286)
  0.003127983 dotest: cmpku  01000000/FFFFFFFF/01000000 (ELAPSED: 0.000467515)
complete

我增强测试套件的原因是我觉得在 cmpki [Krishna 的原始算法] 中使用 signed int 可能有问题对于设置了符号位的数字[因为算术右移与逻辑右移的语义]。而且，因为最初的问题表明数字是无符号的。

我添加了一个未签名的版本并解决了这个问题。

如何使用按位运算符比较两个无符号整数？

How to I use bitwise operators to compare two unsigned integers?

c

logic

boolean