Optimal binary signed-digit representations of integers and the Stern polynomial

The binary signed-digit (BSD) representation of integers is used for efficient integer computation in various settings. The Stern polynomial is a polynomial extension of the well-studied Stern diatomic sequence. In this paper, we show previously unknown connections between BSD integer representations and the Stern polynomial. We then exploit these connections to devise a fast algorithm to count optimal BSD representations on a range of integers and calculate their weights.