0

Two 32 bit integer values A and B, are processed to give the 32 bit integers C and D as per the following rules. Which of the rule(s) is(are) reversible? i.e. is it possible to obtain A and B given c and D in all condition?

A. C = (int32)(A+B), D = (int32)(A-B)

B. C = (int32)(A+B), D= (int32)((A-B)>>1)

C. C = (int32)(A+B), D = B

D. C = (int32)(A+B), D = (int32)(A+2*B)

E. C = (int32)(A*B), D = (int32)(A/B)

A few questions about the integer arithmetic. Modular addition forms amathematical structure known as an abelian group. How about signed addition? It's also commutative (that’s where the “abelian” part comes in) and associative, is this forms a n an abelian group?

Given that integer addition is commutative and associative, C is apparently true, because we can retrieve A by (A+(B-B)). What about D? Can we assume that 2 * B = B + B st. B = A+B+B-(A+B)?

And multiplication is more complicated, but I know that it can not be retrieve A if there is an overflow.

Improve this question
6
  • Only unsigned integer types form groups with respect to addition in C and C++. Signed addition usually can't, already for the simple reason that INT_MIN usually has no inverse in the common 2complement representation. Commented Oct 6, 2013 at 7:44
  • @JensGustedt What about the specific problem above? Commented Oct 6, 2013 at 12:00
  • Take INT32_MIN for A and B and it is implementation defined what will happen in any case, so there is no answer. I get the suspicion that you are trying to get a consistent answer to an ill-posed exercise. Often we see such exercise here that come from not-so-well-informed teachers that take two's complement for granted and never heard of signals that can be raised in case of overflow. Don't do such stuff with int32 (BTW the standard typedef is called int32_t) but with uint32_t. Where do you have these questions from? Commented Oct 6, 2013 at 18:58
  • @JensGustedt Microsoft intern hiring written test. But I've seen it somewhere else. Commented Oct 8, 2013 at 3:33
  • @JensGustedt I don't quit get you. This question is asking you that which one can retrieve A and B even under overflow. I think C is right anyway. Because addition for integers is commutative and associative. So I can retrieve A by E = C - D = A + B - B = A and B by C - E. What do you think? And I take D as a right answer, see my questions. Commented Oct 8, 2013 at 3:38

1 Answer 1

Reset to default
8

This is a quote from 5 [expr] paragraph 4:

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.

What makes overflow for unsigned integers work is defined in 3.9.1 [basic.fundamental] paragraph 4:

Unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer.

Basically this says that you shall not overflow when using signed integer arithmetic. If you do, all bets are off. This implies that signed integers do not form an Abelian group in C++.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

But signed addition is commutative and associative. This is not sufficient for it to form an abelian group? And any suggestions for the specific problem above(the 2nd question)?
@zoujyjs: The rules would need to apply to any value in the group. However, they clearly do not apply, e.g., for A == std::numeric_limits<int>::max() and B == 2 because A + B and A * B both overflow, resulting in undefined behavior.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.