整数的带符号二进制表示数的快速计算

摘要

Binary Signed Digit (BSD) representation of an integer is widely used in computer arithmetic, cryptography and digital signal processing. An integer of length n bits can have several BSD representations. In this paper, the authors studied the properties of the number of BSD representation of an integer, and presented two improved non-recursion algorithms. They can rapidly calculate the exact number of BSD representations of an integer of a certain length, and the storage requirements get reduced.%整数的带符号数字表示广泛应用于计算机算术、密码学、数字信号处理等领域.一个长度为n比特的整数有多种带符号二进制表示.对整数的带符号二进制表示数的性质进行研究,给出了两个改进的非递归算法,所得算法能快速计算给定整数的给定长度的带符号二进制表示数,且降低了空间消耗.