MagicBottle

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:

---

• 𝑥+𝑦=((𝑥 | 𝑦)≪1)−(𝑥⊕𝑦)

And then after shifting right by one on both sides we are left with:

• (𝑥+𝑦)≫1=(𝑥 | 𝑦)−((𝑥⊕𝑦)≫1)

This goes to the ceiling because we are flooring the part we are subtracting via the right shift.

Uh, where did that new subtraction based identity come from?

Working backwards towards another well known identity, if we spell out the left shift with addition we get:

• 𝑥+𝑦=(𝑥 | 𝑦)+(𝑥 | 𝑦)−(𝑥⊕𝑦)

Then using the following identity for exclusive or:

• 𝑥⊕𝑦=(𝑥 | 𝑦)−(𝑥 & 𝑦)

We get the following, being careful with the sign:

• 𝑥+𝑦=(𝑥 | 𝑦)+(𝑥 | 𝑦)−(𝑥 | 𝑦)+(𝑥 &𝑦)

Or:

• 𝑥+𝑦=(𝑥 | 𝑦)+(𝑥 & 𝑦)

Source

Hacker's Delight, Dietz, and HAKMEM. Using pommicket's LaTeX tool, which I wanted an excuse to try.

this is my first post