在溢出事件中携带位 [英] Carry bits in incidents of overflow

问题描述

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
    int isLessOrEqual(int x, int y)
{

  int msbX = x>>31;
  int msbY = y>>31;
  int sum_xy = (y+(~x+1));

  int twoPosAndNegative = (!msbX & !msbY) & sum_xy; //isLessOrEqual is FALSE. 
  // if = true, twoPosAndNegative = 1; Overflow true
  // twoPos = Negative means y < x which means that this 
  int twoNegAndPositive = (msbX & msbY) & !sum_xy;//isLessOrEqual is FALSE
  //We started with two negative numbers, and subtracted X, resulting in positive. Therefore, x is bigger.
  int isEqual = (!x^!y); //isLessOrEqual is TRUE
  return (twoPosAndNegative | twoNegAndPositive | isEqual);
    }

当前，我正在尝试研究如何在此运算符中进行位传送. 此功能的目的是识别int y >= int x.

Currently, I am trying to work through how to carry bits in this operator. The purpose of this function is to identify whether or not int y >= int x.

这是类分配的一部分，因此对转换和我可以使用的运算符有限制.

This is part of a class assignment, so there are restrictions on casting and which operators I can use.

我试图通过应用MSB补码的掩码来考虑一个进位，以尝试从等式中删除最高有效位，以便它们可能溢出而不会引起问题.

I'm trying to account for a carried bit by applying a mask of the complement of the MSB, to try and remove the most significant bit from the equation, so that they may overflow without causing an issue.

我的印象是，忽略溢出情况，返回的运算符将起作用.

I am under the impression that, ignoring cases of overflow, the returned operator would work.

这是我调整后的代码，仍然无法正常工作.但是，我认为这是进步吗?我觉得自己在追自己的尾巴.

Here is my adjusted code, still not working. But, I think this is progress? I feel like I'm chasing my own tail.

推荐答案

提问者已经自已回答他们的问题(班级作业)，因此此时提供替代解决方案似乎是合适的.该问题明确地假定整数表示为二进制补码.

The asker has self-answered their question (a class assignment), so providing alternative solutions seems appropriate at this time. The question clearly assumes that integers are represented as two's complement numbers.

一种方法是考虑CPU如何通过比较指令为条件分支计算谓词.处理器条件代码中表示的小于符号"是SF≠OF. SF是符号标志，符号位的副本或结果的最高有效位(MSB). OF是溢出标志，它指示有符号整数运算中的溢出.计算为符号位或MSB的进位与进位的异或.使用二进制补码运算法则a - b = a + ~b + 1，因此a < b = a + ~b < 0.仍然需要将符号位(MSB)的计算与低位充分分开.这将导致以下代码:

One approach is to consider how CPUs compute predicates for conditional branching by means of a compare instruction. "signed less than" as expressed in processor condition codes is SF ≠ OF. SF is the sign flag, a copy of the sign-bit, or most significant bit (MSB) of the result. OF is the overflow flag which indicates overflow in signed integer operations. This is computed as the XOR of the carry-in and the carry-out of the sign-bit or MSB. With two's complement arithmetic, a - b = a + ~b + 1, and therefore a < b = a + ~b < 0. It remains to separate computation on the sign bit (MSB) sufficiently from the lower order bits. This leads to the following code:

int isLessOrEqual (int a, int b)
{
    int nb = ~b;
    int ma = a  & ((1U << (sizeof(a) * CHAR_BIT - 1)) - 1);
    int mb = nb & ((1U << (sizeof(b) * CHAR_BIT - 1)) - 1);
    // for the following, only the MSB is of interest, other bits are don't care
    int cyin = ma + mb;
    int ovfl = (a ^ cyin) & (a ^ b);
    int sign = (a ^ nb ^ cyin);
    int lteq = sign ^ ovfl;
    // desired predicate is now in the MSB (sign bit) of lteq, extract it
    return (int)((unsigned int)lteq >> (sizeof(lteq) * CHAR_BIT - 1));
}

在最后一次右移之前强制转换为unsigned int是必要的，因为根据ISO-C ++标准第5.8节，带负值的有符号整数的右移是实现定义的.阿斯克(Asker)指出，不允许 进行强制类型转换.当对符号整数进行右移时，C ++编译器将生成逻辑右移指令或算术右移指令.因为我们只对提取MSB感兴趣，所以我们可以通过移出然后屏蔽掉LSB之外的所有其他位来将自己与选择隔离开来，但需要另外进行一次操作:

The casting to unsigned int prior to the final right shift is necessary because right-shifting of signed integers with negative value is implementation-defined, per the ISO-C++ standard, section 5.8. Asker has pointed out that casts are not allowed. When right shifting signed integers, C++ compilers will generate either a logical right shift instruction, or an arithmetic right shift instruction. As we are only interested in extracting the MSB, we can isolate ourselves from the choice by shifting then masking out all other bits besides the LSB, at the cost of one additional operation:

    return (lteq >> (sizeof(lteq) * CHAR_BIT - 1)) & 1;

以上解决方案总共需要进行11或12个基本操作.一种更有效的解决方案是基于1972年的MIT HAKMEM备忘录，其中包含以下观察内容:

The above solution requires a total of eleven or twelve basic operations. A significantly more efficient solution is based on the 1972 MIT HAKMEM memo, which contains the following observation:

第23项(Schroeppel):(A AND B)+(A OR B)= A + B =(A XOR B)+ 2(A AND B).

ITEM 23 (Schroeppel): (A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).

这很简单，因为A AND B代表进位位，而A XOR B代表和位.在2月11日对comp.arch.arithmetic的新闻组发布中. 2000年，Peter L. Montgomery提供了以下扩展名:

This is straightforward, as A AND B represent the carry bits, and A XOR B represent the sum bits. In a newsgroup posting to comp.arch.arithmetic on February 11, 2000, Peter L. Montgomery provided the following extension:

如果XOR可用，则可用于求平均值 总和可能溢出时，两个无符号变量A和B:

If XOR is available, then this can be used to average two unsigned variables A and B when the sum might overflow:

 (A+B)/2 = (A AND B) + (A XOR B)/2

在这个问题的上下文中，这使我们能够计算(a + ~b) / 2而没有溢出，然后检查符号位以查看结果是否小于零.尽管Montgomery仅指无符号整数，但通过使用算术右移可以直接扩展到带符号整数，请记住，右移是一个整数除法，舍入为负无穷大，而不是正整数除以零. >

In the context of this question, this allows us to compute (a + ~b) / 2 without overflow, then inspect the sign bit to see if the result is less than zero. While Montgomery only referred to unsigned integers, the extension to signed integers is straightforward by use of an arithmetic right shift, keeping in mind that right shifting is an integer division which rounds towards negative infinity, rather than towards zero as regular integer division.

int isLessOrEqual (int a, int b)
{
    int nb = ~b;
    // compute avg(a,~b) without overflow, rounding towards -INF; lteq(a,b) = SF
    int lteq = (a & nb) + arithmetic_right_shift (a ^ nb, 1);
    return (int)((unsigned int)lteq >> (sizeof(lteq) * CHAR_BIT - 1));
}

不幸的是，C ++本身没有提供可移植的方法来编写算术右移代码，但是我们可以使用

Unfortunately, C++ itself provides no portable way to code an arithmetic right shift, but we can emulate it fairly efficiently using this answer:

int arithmetic_right_shift (int a, int s)
{
    unsigned int mask_msb = 1U << (sizeof(mask_msb) * CHAR_BIT - 1);
    unsigned int ua = a;
    ua = ua >> s;
    mask_msb = mask_msb >> s;
    return (int)((ua ^ mask_msb) - mask_msb);
}

内联时，当移位计数为编译时常量时，这仅向代码添加了两条指令.如果编译器文档指示通过算术右移指令完成了实现定义的负值带符号整数的处理，则可以安全地简化为以下六个操作的解决方案:

When inlined, this adds just a couple of instructions to the code when the shift count is a compile-time constant. If the compiler documentation indicates that the implementation-defined handling of signed integers of negative value is accomplished via arithmetic right shift instruction, it is safe to simplify to this six-operation solution:

int isLessOrEqual (int a, int b)
{
    int nb = ~b;
    // compute avg(a,~b) without overflow, rounding towards -INF; lteq(a,b) = SF
    int lteq = (a & nb) + ((a ^ nb) >> 1);
    return (int)((unsigned int)lteq >> (sizeof(lteq) * CHAR_BIT - 1));
}

先前在将符号位转换为谓词时使用强制转换的注释也适用于此.

The previously made comments regarding use of a cast when converting the sign bit into a predicate apply here as well.

这篇关于在溢出事件中携带位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！