按位运算等效于大于运算符
我正在研究一个函数，它基本上可以看到两个整数中的哪一个更大。 传递的参数是2个32位整数。 诀窍是允许的唯一操作员! ~ | & <> ^ ! ~ | & <> ^ ! ~ | & <> ^ （没有转换，除了signed int，*，/， – 等其他数据类型。）。
到目前为止，我的想法是将两个二进制文件组合在一起，以查看它们不共享的1值的所有位置。 我想要做的就是取这个值并将最远的1隔离开来。 然后看看它们中的哪一个具有该值。 那个价值就会越大。 （假设我们使用8位整数而不是32位）。 如果传递的两个值是01011011和01101001我在它们01101001使用了^来得到00100010 。 然后我想把它变成00100000换句话说01xxxxxx -> 01000000那么&它的第一个数字!! 结果并将其归还。 如果它是1 ，则第一个#更大。
有关如何01xxxxxx -> 01000000或其他什么帮助的任何想法？
忘记注意：没有ifs，whiles，fors等……
这是一个无循环版本，用于比较O（lg b）操作中的无符号整数，其中b是机器的字大小。 注意OP没有其他数据类型而不是signed int ，所以看起来这个答案的顶部可能不符合OP的规范。 （扰流板版本在底部。）
请注意，我们要捕获的行为是当a的最高有效位不匹配为1且b为0 。 考虑这一点的另一种方式是，大于b相应位的任何位都意味着a大于b ，只要b的较早位不小于b的相应位即可。
为此，我们计算大于b相应位的所有位，同样计算小于b相应位的所有位。 我们现在想要掩盖所有’大于’位低于任何’小于’位的位，所以我们取所有’小于’位并将它们全部涂抹到右边制作一个掩码：最重要的位设置全部从最低位开始的方式现在是1 。
现在我们要做的就是删除使用简单位掩码逻辑设置的“大于”位。
如果a <= b则结果值为0，如果a > b则结果a > b非零值。 如果我们希望在后一种情况下它为1 ，我们可以做一个类似的拖尾技巧，只看一下最不重要的位。
#include // 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; }
我会留下解释为什么它适合你。
一个无符号变量，假设可以使用逻辑（&&，||）和比较（！=，==）。
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而不是：
#include 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!
要将001xxxxx转换为00100000 ，首先执行：
x |= x >> 4; x |= x >> 2; x |= x >> 1;
（这是8位;将其扩展到32，在序列开始时添加8和16的移位）。
这给我们留下了00111111 （这种技术有时被称为“比特涂抹”）。 然后我们可以切掉除前1位之外的所有内容：
x ^= x >> 1;
离开我们00100000 。
Kaganar较小的isGt函数的完全无 分支版本可能如下所示：
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; //1+ on GT, 0 otherwise. diff &= ~(diff >> 1) | 0x80000000; diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff); //flatten back to range of 0 or 1. diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff |= diff >> 16; diff &= 1; return diff; }
这为实际计算提供了大约60条指令（MSVC 2010编译器，在x86拱门上），另外还有10个堆栈操作，用于函数的prolog / epilog。
编辑：
好的，代码有一些问题，但我修改了它，以下工作。
此辅助function比较数字的第n位有效数字：
int compare ( int a, int b, int n ) { int digit = (0x1 << n-1); if ( (a & digit) && (b & digit) ) return 0; //the digit is the same if ( (a & digit) && !(b & digit) ) return 1; //a is greater than b if ( !(a & digit) && (b & digit) ) return -1; //b is greater than a }
以下应递归返回较大的数字：
int larger ( int a, int b ) { for ( int i = 8*sizeof(a) - 1 ; i >= 0 ; i-- ) { if ( int k = compare ( a, b, i ) ) { return (k == 1) ? a : b; } } return 0; //equal }
尽管我不想做别人的作业我无法抗拒这一个.. :)我相信其他人可以想到一个更紧凑的…但这里是我的..工作得很好，包括负数。 。
编辑：虽然有几个错误。 我将把它留给OP找到它并修复它。
#include #include int a, b, i, ma, mb, a_neg, b_neg, stop; int flipnum(int *num, int *is_neg) { *num = ~(*num) + 1; *is_neg = 1; return 0; } int print_num1() { return ((a_neg && printf("bigger number %d\n", mb)) || printf("bigger number %d\n", ma)); } int print_num2() { return ((b_neg && printf("bigger number %d\n", ma)) || printf("bigger number %d\n", mb)); } int check_num1(int j) { return ((a & j) && print_num1()); } int check_num2(int j) { return ((b & j) && print_num2()); } int recursive_check (int j) { ((a & j) ^ (b & j)) && (check_num1(j) || check_num2(j)) && (stop = 1, j = 0); return(!stop && (j = j >> 1) && recursive_check(j)); } int main() { int j; scanf("%d%d", &a, &b); ma = a; mb = b; i = (sizeof (int) * 8) - 1; j = 1 << i; ((a & j) && flipnum(&a, &a_neg)); ((b & j) && flipnum(&b, &b_neg)); j = 1 << (i - 1); recursive_check(j); (!stop && printf("numbers are same..\n")); }
我想我有3个操作的解决方案：
在第一个数字中加一个，从可以表示的最大数字中减去它（全1）。 将该号码添加到第二个号码。 如果它溢出，那么第一个数字小于第二个数字。
如果这是正确的，我不是100％肯定。 那你可能不需要加1，我不知道是否可以检查溢出（如果不是那么只保留最后一位并测试它是否为1）。
编辑：约束使得底部的简单方法无效。 我正在添加二进制搜索function和最终比较以检测更大的值：
unsigned long greater(unsigned long a, unsigned long b) { unsigned long x = a; unsigned long y = b; unsigned long t = a ^ b; if (t & 0xFFFF0000) { x >>= 16; y >>= 16; t >>= 16; } if (t & 0xFF00) { x >>= 8; y >>= 8; t >>= 8; } if (t & 0xf0) { x >>= 4; y >>= 4; t >>= 4; } if ( t & 0xc) { x >>= 2; y >>= 2; t >>= 2; } if ( t & 0x2) { x >>= 1; y >>= 1; t >>= 1; } return (x & 1) ? a : b; }
我们的想法是从我们感兴趣的单词中最重要的一半开始，看看是否有任何设置位。 如果有，那么我们不需要最不重要的一半，所以我们将不需要的位移开。 如果没有，我们什么也不做（无论如何，一半是零，所以它不会妨碍）。 由于我们无法跟踪移位量（它需要添加），我们也会移动原始值，以便我们可以进行最终操作and确定更大的数字。 我们用前一个掩码的一半大小重复这个过程，直到我们将有趣的位折叠到位0。
我没有故意在这里添加相同的案例。
老答案：
最简单的方法可能是家庭作业的最佳方法。 一旦你得到了不匹配的位值，你就可以从0x80000000处的另一个掩码（或者你的字大小的任何合适的最大位位置）开始，并保持右移，直到你达到你的不匹配值中设置的位。 如果右移最终为0，则不匹配值为0。
我假设您已经知道确定较大数字所需的最后一步。