Average number of multiplications in left-to-right k-ary exponentiation
In Algorithm 14.82, you divide the exponent into $2^k$ windows. In the pre-compute stage, you encode those &quot;bit-windows&quot; into products of $x$. All of those bit-windows will be involved in multiplications except the $000...00_2$ window, which will be encoded as 1, hence no multiplication (I'm assuming $x\cdot 1$ is trivial).
Here's the trick: on average you're equally likely to be using the other $2^k - 1$ bit-windows. Another way of saying this is that you have a probability $\frac{2^k-1}{2^k}$ to pick a bit-window that isn't $000...000_2$. How many bit-windows did we split the exponent into? Precisely $\lfloor{t/k}\rfloor$, or $l$.
So the average number of multiplications (that aren't pre-computations or squarings) is $l\cdot \frac{2^k-1}{2^k}$. You don't have to worry about the evenness of the residual bits at all.
Advice
In practice, 14.85 (the sliding window method) is more efficient in practice, even if it's hard to count the number of steps it takes (as noted on page 617). If you're trying to implement something, check that one out. As a real-world example, CPython, the usual C implementation of Python, uses 14.82 for large modular exponentiation. They choose $k=5$ as that seems to work well in practice.
Example
I copied an example from here to count the multiplications.
Looking at Algorithm 14.82 on page 615, let's say I wanted to calculate $x^{250}$ and let $k=2$, or $b=2^2=4$. Write $250 = (11111010)_2$. With a window of $2$, you have $11|11|10|10$.
First, let's make the pre-computation table: even though we only need $11_2$ and $10_2$, let's follow 14.82 anyway:
$00_2\rightarrow 1$
$01_2\rightarrow x$
$10_2\rightarrow x\cdot x = x^2$
$11_2\rightarrow x^2 \cdot x = x^3$
We have four &quot;bit-windows&quot;, only $3 = 4-1$ of which will be involved in multiplying something that isn't $1$.
Now, in the algorithm, step 3.1 is the &quot;squaring&quot; step, except we're multiplying by $x^{2^2}$ each time. After each &quot;squaring&quot; step, we have a multiplication step using the table above. So taking the bits two at a time we have:
$11_2: x^3, x^3$
$11_2: (x^3)^4=x^{12}, x^{12}\cdot x^3 = x^{15}$
$10_2: (x^{15})^4=x^{60}, x^{60}\cdot x^2 = x^{62}$
$10_2: (x^{62})^4=x^{248}, x^{248}\cdot x^2 = x^{250}$
The middle column is the squaring step (3.1), and the right column is the multiplication step (3.2).
So that gives us $2$ multiplications in the precompute stage, $6$ squarings (or $3$ &quot;raising to the fourths&quot;), and $3$ multiplications.
In this example, $t=8$, so $l = 4, 2^k = 4$, so the formula gives $4 \cdot 3/4 = 3$.
If you do the same thing with $k=3, b = 8$, you get $6$ precompute multiplications, $6$ squarings, and $2$ multiplications. In that case, our formula gives $l = \lfloor{8/3}\rfloor = 2$, and $2^k = 8$, so we calculate $14/8 \approx 2$ multiplications. Close enough?