C/C++ Integer Operation [closed]
Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 13 years ago.
Improve this questionI found by chance that
int a = (h/2)*w+ ( (h+1)/2-h/2 ) 开发者_运维问答 * (w+1)/2 ;
is equal to
int b = (w * h + 1) / 2 ;
when w and h are positive integers (assume no overflow).
Can you show me why these 2 are the same?
edit : integer -> positive integer.
In order to simplify your expression, you will have to consider four cases:
- h even and w even
- h even and w odd
- h odd and w even
- h odd and w odd
From there, and applying the appropriate integer truncation rules, you should be able to simplify to your second expression.
Actually this is a math problem: (integer)/2 should be interpreted as floor. So, the problem is:
Show that
floor(h/2)*w + ( floor((h+1)/2) - floor(h/2) ) * floor((w+1)/2)
is equivalent tofloor((w*h+1)/2)
Proof:
- h = 2k, w = 2l: (both numbers are even) ...
- h = 2k + 1, w = 2l: ...
- h = 2k, w = 2l + 1: ...
- h = 2k + 1, w = 2k + 1: ...
A hint: floor((2k+1)/2) == k
. You can easily show the equivalence.
For example, the case 4:
a) floor(2k+1/2)*(2l+1) + ( floor((2k+2)/2) - floor((2k+1)/2) ) * floor((2l+2)/2) = 2kl+k + (k+1 - k)*(l+1) = 2kl + k + l + 1
b) floor(((2k+1)*(2l+1)+1)/2) = floor((4kl+2k+2l+2)/2) = 2kl + k + l + 1
Therefore, the two equations are equivalent.
Funny, the question says that it's equal and it seems like it when you test few even and odd values. But that's easy boring math, so nobody check all cases. I was also lazy, and, even if I am more a math guy, I did a quick computer check using few copy-paste:
bool diff = false;
int n = 100;
for(int w = -n; w<n; ++w){
for(int h = -n; h<n; ++h){
int a = (h/2)*w+ ( (h+1)/2-h/2 ) * (w+1)/2 ;
int b = (w * h + 1) / 2;
if (a!=b) diff = true;
}
}
cout << (diff ? "a != b" : "a == b") << endl;
And I found that it's not equal for w = -1 and h =-1, easy to check that then a = 0 and b = 1. This is how "nice simplification" often introduces new bug.
PS: To be fair, I am guessing that w and h are width and height, so they are probably always positive. But that was not specified (and, by experience, some other code may return negative width)
This is a direct mathematical question. Just prove the following:
(h/2)*w+ ( (h+1)/2-h/2 ) * (w+1)/2 = (w * h + 1) / 2
精彩评论