Floor
How do you compute ⌊𝑥+𝑦2⌋ without overflow in 𝑥+𝑦 ?
We can decompose the addition into two parts, an addition with carries ignored (XOR) and one with the carries, shifted into place:
- 𝑥+𝑦=(𝑥⊕𝑦)+((𝑥 & 𝑦)≪1)
We shift right by one on both sides, cancelling out the shift left:
- (𝑥+𝑦)≫1=((𝑥⊕𝑦)≫1)+(𝑥 & 𝑦)
Ceiling
If you want to calculate ⌈𝑥+𝑦2⌉ however, we can use a different, more exciting identity for addition that uses subtraction: