在不使用任何算术运算符或比较运算符的情况下，如何使用逐位运算符来查看两个无符号整数中的哪个较大？
让我们考虑两个整数4(0100(和3(0011(。我们需要生成区分两个整数的最大子位序列，例如上面的是0100(因为第三个位不同(，然后我们可以通过进行位AND运算来简单地知道哪个更大：
0100 & 0100 = 0100 > 0
0011 & 0100 = 0
代码如下：
#include <stdio.h>
int main()
{
int a, b;
printf("Enter two numbersn");
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 equaln");
return 0;
}
return 0;
}
如果你处理的是数字的十进制表示，你会说数字最多的是较大的。
如果两个数字的位数相同怎么办？好吧，你依次比较每个数字，从最重要的数字开始。
用十进制表示，这很难满足您的要求。但在二进制中，我们可以进行简单的真值测试。因此，这种方法可以在这里使用。
+---+---+---+---+ +---+---+---+---+
| 0 | 1 | 1 | 0 | 6 | 0 | 1 | 1 | 0 | 6
+---+---+---+---+ +---+---+---+---+
→ ↑ ↑ → → ↑ ↑
+---+---+---+---+ +---+---+---+---+
| 0 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 0 | 4
+---+---+---+---+ +---+---+---+---+
因此，这适用于相同大小的无符号整数：
- 隔离每个数字的最高有效位
- 如果它们不同，则哪一个的位集更大
- 如果没有，则重复下一个最高有效位
有一个更简单的解决方案，涉及到找到两个输入数字的异或。
在循环中使用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=%dn",
a,b,cmps,cmpx);
code = 1;
break;
}
}
if (code)
break;
}
if (code == 0)
printf("completen");
return code;
}
更新：
我增强了诊断测试套件。而且，我添加了一些基准测试。
我还添加了两个源自克里希纳答案的函数。
#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=%dn",
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("completen");
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[克里希纳的原始算法]中使用签名int可能会对带有符号位集的数字产生问题[因为算术右移与逻辑右移的语义]。而且，因为最初的问题表明这些数字是无符号的。
我添加了一个未签名的版本，解决了这个问题。