Fast calculation of number of binary signed digit representations of an integer

doi:10.3724/SP.J.1087.2012.03121

Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (11): 3121-3124.DOI: 10.3724/SP.J.1087.2012.03121

Previous Articles Next Articles

Fast calculation of number of binary signed digit representations of an integer

LI Zhong¹,²,PENG Dai-yuan²

1. School of Computer and Information Engineering,Yibin University,Yibin Sichuan 644000,China
2. School of Information Science and Technology,Southwest Jiaotong University,Chengdu Sichuan 610031,China

Received:2012-04-17 Revised:2012-06-15 Online:2012-11-12 Published:2012-11-01
Contact: LI Zhong
Supported by:
A Project Supported by Scientific Reserch Fund of SiChuan Provincial Education Department

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

李忠¹,²,彭代渊¹

1. 西南交通大学信息科学与技术学院，成都 610031
2. 宜宾学院计算机与信息工程学院，四川宜宾 644000

通讯作者: 李忠
作者简介:李忠(1963-),男,四川安岳人,副教授,博士,主要研究方向:密码学、信息安全；彭代渊(1955-),男,四川资阳人,教授,博士生导师, 博士,主要研究方向:密码学、信息安全、编码理论。
基金资助:
四川省教育厅重点科研资助项目(07ZA145)

Abstract

Abstract: 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.

Key words: integer, binary signed digit representation, number of representation, recursion algorithm, nonrecursion algorithm

摘要： 整数的带符号数字表示广泛应用于计算机算术、密码学、数字信号处理等领域。一个长度为n比特的整数有多种带符号二进制表示。对整数的带符号二进制表示数的性质进行研究，给出了两个改进的非递归算法，所得算法能快速计算给定整数的给定长度的带符号二进制表示数，且降低了空间消耗。

关键词: 整数, 带符号二进制表示, 表示数, 递归算法, 非递归算法

CLC Number:

TP301.6

LI Zhong PENG Dai-yuan. Fast calculation of number of binary signed digit representations of an integer[J]. Journal of Computer Applications, 2012, 32(11): 3121-3124.

李忠彭代渊. 整数的带符号二进制表示数的快速计算[J]. 计算机应用, 2012, 32(11): 3121-3124.

[1]	MA Minyao, LIU Zhuo, XU Yi, WU Lian. Private-preserving determination problem of integer-interval positional relationship [J]. Journal of Computer Applications, 2020, 40(9): 2657-2664.
[2]	MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship [J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.
[3]	LIU Zongfu, YUAN Zheng, ZHAO Chenxi, ZHU Liang. Integral attack on PICO algorithm based on division property [J]. Journal of Computer Applications, 2020, 40(10): 2967-2972.
[4]	YANG Xiaohua, GUO Jianquan. Multi-period multi-decision closed-loop logistics network for fresh products with fuzzy variables [J]. Journal of Computer Applications, 2019, 39(7): 2168-2174.
[5]	SUN Yiru, LIANG Xiangqian, SHANG Yufang. Identity based ring signature scheme in ideal lattice [J]. Journal of Computer Applications, 2016, 36(7): 1861-1865.
[6]	WU Qingxia, ZHOU Ya, WEN Diyao, HE Zhenghong. Personalized trip itinerary recommendation based on user interests and points of interest popularity [J]. Journal of Computer Applications, 2016, 36(6): 1762-1766.
[7]	JING Shibo, YANG Liming, LI Junhui, ZHANG Siyun. Semi-supervised extreme learning machine and its application in analysis of near-infrared spectroscopy data [J]. Journal of Computer Applications, 2016, 36(2): 387-391.
[8]	YANG Jie, GAO Hong, LIU Tao, LIU Wei. Integrated berth and quay-crane scheduling based on improved genetic algorithm [J]. Journal of Computer Applications, 2016, 36(11): 3136-3140.
[9]	ZHOU Jingxian, HU Zhihua. Scheduling optimization for cross-over twin automated stacking cranes in automated container terminal [J]. Journal of Computer Applications, 2015, 35(9): 2673-2677.
[10]	CHEN Wenxin, SHAO Liping, SHI Jun. Iterative adaptive reversible image watermarking algorithm combined with mean-adjustable integer transform [J]. Journal of Computer Applications, 2015, 35(7): 1908-1914.
[11]	YUAN Yanan, WANG Peng, LIU Feng. Performance analysis of multi-scale quantum harmonic oscillator algorithm [J]. Journal of Computer Applications, 2015, 35(6): 1600-1604.
[12]	WANG Guangsai, ZENG Guang, HAN Wenbao, LI Yongguang. Fast greatest common divisor algorithm based on k-ary reduction [J]. Journal of Computer Applications, 2015, 35(6): 1673-1677.
[13]	ZHANG Lei, YANG Chenghu, LU Meijin. Optimal strategy for production-distribution network of perishable products based on WCVaR [J]. Journal of Computer Applications, 2015, 35(2): 566-571.
[14]	ZHENG Hongxing, WU Yue, TU Chuang, LIU Jinping. Quay crane allocation and scheduling joint optimization model for single ship [J]. Journal of Computer Applications, 2015, 35(1): 247-251.
[15]	GAO Chaofeng XIAO Ling HU Zhihua. Hub-and-spoke network design with constraint of hub cost for less-than-truckload logistics [J]. Journal of Computer Applications, 2014, 34(10): 3034-3038.

Fast calculation of number of binary signed digit representations of an integer

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics