How to replace floor to ceil After severals days I come up with the following formula (here >> is a right bit shift, x and N are integers, N >= 0). And you can just assume that it is correct.

I've got a feeling that right part could be reduced to the following form:

I spend several days trying to figure out the way, but still have no results
 A: Consider two cases.
In the first case, if $A$ is divisible by $B$. Then $\dfrac AB$ is an integer and
$$\left\lfloor\frac AB\right\rfloor = \frac AB = \left\lceil\frac AB\right\rceil,$$
but $\dfrac{A - 1}B < \dfrac AB$ and
$$\left\lfloor\frac{A - 1}B\right\rfloor = \left\lfloor\frac AB\right\rfloor - 1
 = \left\lceil\frac AB\right\rceil - 1.$$
In the second case, $A$ is not divisible by $B.$ Then
$$\left\lfloor\frac{A - 1}B\right\rfloor = \left\lfloor\frac AB\right\rfloor
 = \left\lceil\frac AB\right\rceil - 1.$$
In either case,
$$\left\lfloor\frac{A - 1}B\right\rfloor = \left\lceil\frac AB\right\rceil - 1$$
so
$$\left\lfloor\frac{A - 1}B\right\rfloor + 1 = \left\lceil\frac AB\right\rceil.$$
Let $A = x$ and $B = 2^N,$ and you have your result.

The proof above is closely related to one you have already seen, so as a bonus,
here is a proof of the original formula.
For an arbitrary positive integer $x,$
we assume that $-x$ (a negative number)
is represented by a two's-complement binary integer
in a storage location that is $L$ bits wide, where $2^{L - 1} \geq x.$
The bits in this storage location are then exactly the same as the unsigned binary integer representation of $2^L - x$ and the leftmost bit is a "one".
We further assume that the right-shift operator applied to a negative signed integer inserts "one" bits on the left as it shifts bits off to the right.
Notice that
$$ 2^L - x = (2^L - 1) - (x - 1),$$
where $2^L - 1$ is just a string of $L$ "one" bits, and the subtraction merely cancels any "one" bits in $2^L - 1$ that align with "one" bits in $x - 1.$
There are no "borrow" operations; the result in each bit is unaffected by the bits to its right.
So you can obtain $-x$ right-shifted $N$ bits (for $N\geq 0$) as follows:
On one line write the bits of $2^{L + N}-1,$ that is, a string of $L + N$ "one" bits.
On the line below, write the bits of $x - 1$, with the last bit under the last bit of the line above.
On the third line, write the difference $(2^{L + N}-1) - (x - 1).$
Shift all three lines $N$ bits to the right; that is, erase the rightmost $N$ columns of bits.
You now have one line containing the bits of $2^L - 1$ (a string of $L$ "one" bits),
the line below containing the bits of $\left\lfloor \dfrac{x - 1}{2^N} \right\rfloor$,
and the third line containing the bits of $-x$ shifted $N$ bits to the right;
but the third line is also the difference of the first two lines,
$$ (2^L - 1) - \left\lfloor \dfrac{x - 1}{2^N} \right\rfloor. $$
We write this as
$$ 2^L - \left( \left\lfloor \dfrac{x - 1}{2^N} \right\rfloor + 1 \right), $$
which is the two's-complement representation in $L$ bits of the negative number
$$ - \left( \left\lfloor \dfrac{x - 1}{2^N} \right\rfloor + 1 \right). $$
That proves the formula for positive $x.$
If $x$ is not positive, then $-x$ is non-negative and shifting $-x$ right by $N$ bits has exactly the same result as shifting an unsigned binary integer right by $N$ bits, that is, the result is
$$ \left \lfloor \frac {-x}{2^N} \right\rfloor. $$
Note that
$$ \left \lfloor \frac {-x}{2^N} \right\rfloor
 = - \left \lceil \frac {x}{2^N} \right\rceil, $$
and as we have already shown,
$$ \left \lceil \frac {x}{2^N} \right\rceil = 
   \left \lfloor \frac {x - 1}{2^N} \right\rfloor + 1. $$
Therefore the result of shifting $-x$ right by $N$ bits is
$$ -\left(\left \lfloor \frac {x - 1}{2^N} \right\rfloor + 1\right). $$
That proves the formula for non-positive $x.$

I would just like to point out here that what all these formulas come down to is the simple fact that if $y$ is a binary integer, then the result of shifting $y$ to the right $N$ bits (for $N\geq 0$) is
$$ \left \lfloor \frac {y}{2^N} \right\rfloor, $$
which is relatively obvious if $y \geq 0$ and only slightly less obvious
(but still true) if $y < 0.$
I think this is the simplest way of representing a right-shift for either positive or negative binary integers.
A: It is clear that $$\left \lfloor \dfrac{x-1}{2^N} \right \rfloor +1 = \left \lceil \dfrac{x}{2^N} \right \rceil$$ works for any number $x$ satisfying $k \cdot2^N<x< (k+1)\cdot 2^{N}$ (where $k$ is an integer), as when the number $x$ is strictly in that range, the floor and the ceil is different by 1. To be clearer, the left-hand side will always give you $k +1$ as $$k \cdot2^N<x< (k+1)\cdot 2^{N}$$
$$\Leftrightarrow k \cdot2^N + 1 \leq x < (k+1)\cdot 2^{N}$$
$$\Leftrightarrow k \leq \dfrac{x-1}{2^N} < \dfrac{(k+1)\cdot 2^{N}-1}{2^N} < k+1$$
$$\Rightarrow \left \lfloor \dfrac{x-1}{2^N} \right \rfloor = k$$
and the right-hand side will give you $k+1$, too
Let examine the case when $x=k \cdot 2^N$, the left-hand side will give us $k-1+1=k$, and the result in the right-hand side is clearly $k$.
