Reputation: 142
I am trying to reproduce the output of the following function using only the bit-wise operators ! ~ & ^ | + << >>.
int test_dl2(int x, int y) {
long long lsum = (long long) x + y;
return lsum == (int) lsum;
}
All of my testing shows that the answer to everything is just 1. However the auto-tester that tells you if a question is right says just returning one is not correct.
In what situations to this is the answer not 1? And if the function is not replicated like so:
int test_dl2(int x, int y) {
return 1;
}
What would the correct function/expression be (Using only the said bitwise operators)?
Upvotes: 0
Views: 117
Reputation: 11567
Maybe you are trying to check if the addition of x and y will give a valid result as an uint32_t. The problem, as already stated in the comments, is that if the number is too "large", conversion from uint64_t to uint32_t is undefined.
Presently neither C nor C++ assume that numbers are represented as two's complement and making this kind of verification is difficult. This is going to change as the next C++ standard will enforce the use of two's complement to code signed integers (and presumably the C standard will follow).
But this will not give a meaning to an incorrect conversion and your code will still be invalid.
Some tests can be done, if we assume that the numbers are coded in two's complement (and this is already the behavior in most computers).
Several solutions can be used. Here is one that mostly relies on bitwise operators.
Outline of the method is:
left shift numbers to divide them by two (assumes left shifts on signed are arithmetic, which is true on most computers, but not required presently by the standard)
add them. This will compute x/2+y/2 and it will be equal to (x+y)/2 except if both LSB of x and y are ones, in which case there is a carry generated at weight 2^1 in x+y.
We test the existence of this carry by anding the LSB of x and y and we add it to the sum.
the result of the previous computation (x+y)/2 is always valid on 32 bits. We check if it is valid on 31 bits. If it is true, x+y will be valid on 32 bits.
Checking for this validity is simply done by comparing bits 31 and 30. If they are equal, the result can be converted on 31 bits safely. Otherwise, conversion will induce a sign change.
int is_add32_valid(uint32_t x, uint32_t y) {
uint32_t z = (x>>1) + (y>>1) + (x & y & 0x1) ;
return !( (z ^ (z <<1)) & (1 << 31) ) ;
}
Upvotes: 1
Reputation: 9173
The following test returns 0
for your function:
#include <stdio.h>
#include <limits.h>
int test_dl2(int x, int y) {
long long lsum = (long long) x + y;
return lsum == (int) lsum;
}
int main() {
printf("%d", test_dl2(INT_MAX, 1));
return 0;
}
The number that I used is the maximum of int
which causes overflow. Your code is for testing overflow in int
, so you need to test it with values that causes overflow in +
for int
. There are a lot of tests to show this overflow and mine is just an example.
Update:
As mentioned in comments, lsum == (int) lsum
part in your code in implementation-defined in C
, so you cannot relay in function results at all. My argument is correct if data types were unsigned (unsigned int
and unsigned long long
). This code is also implementation defined till C++20
in C++
. After C++20
, it is defined in C++
again.
Upvotes: 1
Reputation: 135
It should return 0 if x + y is greater then tmax or smaller then tmin.
Otherwise it will return 1.
Upvotes: 0