understanding CalcTreeWidth in bitcoin Merkle tree implementation

Question

I'm trying to understand this bitshifting function:

/** helper function to efficiently calculate the number of nodes at given height in the merkle tree */
    unsigned int CalcTreeWidth(int height) const {
        return (nTransactions+(1 << height)-1) >> height;
    }

I tried running the function by hand and I can see that it produces correct result but I don't get it, I understand that the part : (1 << height)-1) basically sets N=height bits to 1, what I don't understand is the next part.

Why does adding the number of leafs and shifting right height times result in the number of node on that level?

Answer 1

It's doing nTransactions >> height but rounding up instead of rounding down.

nTransactions >> height is nTransactions / (1 << height). By adding (1 << height) - 1 we make it so that if nTransactions isn't an exact multiple of 1 << height then the result is 1 greater.