logo标签列表

C中用于查找小于的位运算符

cbitwise-operators
8
这是一项作业任务，要求我编写一个函数，使用位运算符( ! ~ & ^ | + << >> )判断x < y，如果是，则必须返回1。我只能使用常量0-0xFF，并假设为32位整数。不允许使用循环、转换等操作。

我的想法是，如果只检查4位，可以使用x - y来确定x是否小于y。如果x是8，y是9，结果将是-1的1111。

int lessThan(int x, int y){
    int sub = x + (~y+1);

我困惑的是如何将结果与x进行比较，以确定它确实小于y。我一直在研究这篇文章here，但是对此问题的处理方法有些困惑。我已经解决了移位以获得位扩展，但对如何使用该结果进行值的比较（大于或小于）感到困惑。我只是希望得到一些指导和清晰度，而不是解决方案，这并不是我的意图。
2
“!”和“+”何时成为位运算符的？你确定它们是合法的吗？ - itsme86
是的，我确定它们是合法的。我想我应该说我只能使用这些算术和逻辑运算符。抱歉。 - jwl4
1
允许使用整数和无符号整数。 - jwl4
5
我熟悉这个作业和这个课程。不是给你答案，而是给你一个尝试的方法：考虑x和y的符号，然后将比较分为四种情况。从那里开始简化解决方案。 - user1354557
谢谢，我觉得那就是我一直在苦恼的问题。 - jwl4
5个回答
3
我认为可以通过以下步骤实现：
  1. 对两个数字进行异或操作，得到不同的位
  2. 获取不同的最高有效位（即使这一位发生变化也会有差异）
  3. 检查这个最高有效位是否属于较大的值

代码：

int less(int x, int y) {
    //Get only diffed bits
    int msb = x ^ y;
    //Get first msb bit
    msb |= (msb >>  1);
    msb |= (msb >>  2);
    msb |= (msb >>  4);
    msb |= (msb >>  8);
    msb |= (msb >> 16);
    msb = msb - (msb >> 1);
    //check if msb belongs to y;
    return !((y & msb) ^ msb);
}
1

实现减法的想法很好。

int sub = x + (~y+1);

从这里开始，您只需要检查sub是否为负数，即提取其符号位。这就是技术难点所在。
假设x和y是无符号32位整数。那么减法的结果可以用一个有符号的33位整数表示（检查其最小值和最大值即可）。也就是说，直接使用表达式x + (~y+1)是没有帮助的，因为它会溢出。
如果x和y是31位无符号数字呢？那么，x + (~y+1)可以用一个32位有符号数字来表示，它的符号位告诉我们x是否小于y：
answer(x, y) := ((x + (~y+1)) >> 31) & 1

将32位的x和y转换为31位，将它们的MSB（最高有效位）和其他31位分别存储到不同的变量中：

msb_x = (x >> 31) & 1;
msb_y = (y >> 31) & 1;
x_without_msb = x << 1 >> 1;
y_without_msb = y << 1 >> 1;

接下来考虑它们最高有效位的4种可能组合：

if (msb_x == 0 && msb_y == 0)
    return answer(x_without_msb, y_without_msb);
else if (msb_x == 1 && msb_y == 0)
    return 0; // x is greater than y
else if (msb_x == 0 && msb_y == 1)
    return 1; // x is smaller than y
else
    return answer(x_without_msb, y_without_msb);

将所有这些 if 语句转换为一个庞大而丑陋的逻辑表达式是“读者的练习”。
0

我想在这个讨论中补充一点，因为我不确定是否已经提到过。有些人在这里提到了

( x + ((~y) + 1)) >> 32) & 0x1

对于溢出条件，该方法不起作用。对于二进制补码数字，整数x和y相加的溢出条件为：

x > 0，y > 0，(x+y) < 0

x < 0，y < 0，(x+y) > 0

在这种情况下，我们将x和（-y）相加，必须在确定（x-y）<0之前也检查溢出条件。

long isLess(long x, long y) {
    long xs= (x>>63) & 0x1L; 
    long ys= (y>>63) & 0x1L;
    long s = x + (~y +1L);

    long ss= (s>>63) & 0x1L;

    /*
    //Code without SOP result for clarity
    if(xs & ~ys & ~ss) return 1;
    if(~xs & ys & ss)  return 0;

    return ss;
    */

    return (((xs | ~ys | ~ss) & (~xs | ys | ss)) & ss) |
           (((~xs & ys & ss) | (xs & ~ys & ~ss)) & ~ss);
}
0

这是我的尝试（编译结果，如果 x > y 则返回 0，如果 x < y 则返回 1，如果 x == y 则返回 1）：

((((x + ~y) >> 31) + 1))^1
2
我认为你需要先加1。在二进制补码中，-y = ~y+1。 - UmNyobe
1
这可能对于作业任务来说足够好了，但当出现溢出时它会失败。 - Eric Postpischil
1
3 < 3 什么时候成立了？ - MD XF
-1
为了知道是否 x < y，你可以简单地询问 x - y < 0 的结果是什么。
换句话说，x - y 的结果的符号是什么。
由于您已经声明要假设32位整数，以下将提供正确的结果：
((x - y) >> 31) & 0x1
在进行符号扩展移位时，添加了& 0x1。 - Yaniv Shaked
@ChrisDodd 正确。 - Yaniv Shaked
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接