C/C++ Integer Operation

Question

I 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.

Answer 1

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.

Answer 2

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 to floor((w*h+1)/2)

Proof:

1. h = 2k, w = 2l: (both numbers are even) ...
2. h = 2k + 1, w = 2l: ...
3. h = 2k, w = 2l + 1: ...
4. 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.

Answer 3

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)

Answer 4

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