  The binary signed-digit representation of integers is used for efficient
computation in various settings. The Stern polynomial is a polynomial extension
of the well-studied Stern diatomic sequence, and has itself has been
investigated in some depth. In this paper, we show previously unknown
connections between BSD representations and the Stern polynomial.
  We derive a weight-distribution theorem for $i$-bit BSD representations of an
integer $n$ in terms of the coefficients and degrees of the terms of the Stern
polynomial of $2^i-n$. We then show new recursions on Stern polynomials, and
from these and the weight-distribution theorem obtain similar BSD recursions
and a fast $\mathcal{O}(n)$ algorithm that calculates the number and number of
$0$s of the optimal BSD representations of all of the integers of NAF-bitlength
$\log(n)$ at once, which then may be compared.
