十進制整數轉換為二進制整數的快速方法

劉 碩 彭 雷

(1.荊門市第一中學 荊門 448000)(2.中國地質大學計算機學院 武漢 430074)

十進制整數轉換為二進制整數的快速方法

劉 碩1彭 雷2

(1.荊門市第一中學 荊門 448000)(2.中國地質大學計算機學院 武漢 430074)

將人類使用的十進制數據轉換為計算機使用的二進制數據,是計算機領域的一個重要問題。十進制整數轉換為二進制整數的經典方法就是“除基倒取余”,數據較大時既不方便又容易出錯。論文基于二進制整數各位的權值滿足超遞增序列以及二進制數的數符只有0和1兩種情況的特有屬性,提出了一種十進制整數轉換為二進制整數的快速方法。文中也給出了該轉換方法的一些具體轉換實例,結果表明:該轉換方法,比經典的“除基倒取余”轉換方法更簡單高效,當數據規模較大時,轉換效率更高。

十進制整數; 二進制整數; 整數轉換; 超遞增序列

Class Number TP301

1 引言

不同進制的數據主要包括三個要素:數符、各位的權值及進借位的原則[1～2]。數符就是構成這種進制數的符號,每種進制的數據就表示這種進制的數據有多少個數符。比如我們日常生活中應用最為廣泛的十進制數據,主要包括0、1、2、3、4、5、6、7、8、9共10個數符[3～4]。各位的權值表示當前進制的數據某一位對數據的貢獻,其權值的冪依小數點為中心,往左的各位權值的冪方分別為0、1、2、3…,往右各位的權值的冪方分別為-1、-2、-3…[5]。由于十進制數據是人類最常用的數據,所以通常都需要將其它進制的數據轉換成十進制的數據。轉換的方法就是將非十進制數據的每一個數符與該位的權植相乘,將各位相乘的結果累加起來,即為該數據表示的對應十進制數據[6～7]。例如:十進制數1234.567,依小數點為中心,各位的權值分別為:103、102、101、100、10-1、10-2、10-3,1234.567表示的十進制數是由各位的權值乘以各位的數符然后相加得到,即:1*103+2*102+3*101+4*100+5*10-1+6*10-2+7*10-3。類似地,(1011.01)2,依小數點為中心,各位的權值分別為:23、22、21、20、2-1、2-2,(1011.01)2表示的十進制數是由各位的權值乘以各位的數符然后相加得到,即:1*23+0*22+1*21+1*20+0*2-1+1*2-2=11.25。進借位是數據加減時位數擴展的原則:相加時逢基數進一,相減時借一當基數,比如十進制數據進位時“逢十進一”,兩個十進制數6+7超過了基數10需要進位,因此結果為13。同樣地,兩個二進制數(1)2+(1)2的結果為基數2,因此需要進一位,所以結果為(1)2+(1)2=(10)2。

馮諾依蔓計算機工作原理的核心思想就是計算機工作在二進制狀態[8～9]。計算機中的所有信息,包括圖片、視頻、音頻、文字、數據,全部都以二進制的形式存在。而自然界中,人類使用的數據是十進制。為了便于人類將現實生活中的數據轉換為計算機中的數據,因此如何將十進制數據轉換為二進制數據就成為計算機領域的一個非常重要的問題。

本文基于二進制整數各位的權值滿足超遞增序列的特有屬性,并結合二進制數的數符只有0和1兩種情況,每一位數符對整個數據的貢獻或者就是該位的權值,或者對整個數據沒有任何貢獻的關系,提出了一種十進制整數轉換為二進制整數的快速方法。

2 經典的“除基倒取余”轉換方法

十進制數據轉換為二進制數據的過程中,尤以十進制整數轉換為二進制整數最為常見[10]。目前,十進制整數轉換為二進制整數的經典方法就是“除基倒取余”,即用十進制整數整除二進制的基數2,直至商為0時結束[11～12]。在整除的過程中,每一步得到一個余數。由于是整除2,所以余數只有0和1兩種。整除結束以后,將得到的余數按從后到前的倒序排列,所得的結果即為轉換后對應的二進制數據。例如:圖1給出了十進制整數21,按“除基倒取余”轉換成2進制后的結果,即(21)10=(10101)2。這種方法簡明扼要地給出了十進制整數轉換成二進制整數的方法。然而,當十進制整數較大的時候,這種轉換方法比較費時,一不小心也非常容易將0與1弄錯[13]。

3 快速轉換方法的基本思想

證明 用歸納法進行證明。

1) 取j=1,有21=2>20=1;

則定理1得證。

2726252423222120

即:128 64 32 16 8 4 2 1。

根據定理1可知,64>32+16+8+4+2+1,類似地,8>4+2+1。

定理1表明,二進制整數從低位到高位的每一位權值,正好是超遞增序列。

圖1 十進制整數轉換為二進制整數的經典“除基倒取余”法

4 快速轉換實例

由于二進制整數從低位到高位的每一位權值正好是超遞增序列。同時,二進制的數符只有0和1兩種,如果某位的數符為0,則0與該位的權值相乘仍然為0,即表示該位數符對于整個數據沒做任何貢獻。如果某位的數符為1,則1與該位的權值相乘結果為該位的權值,即表示該位數符對于整個數據的貢獻即為該位數據的權值。因此,任意十進制整數轉換成二進制整數時,可以不用“除基倒取余”的方法,而是根據定理1即可快速得到。例如,我們仍然用十進制整數21為例來說明,由于25>21>24,顯然,十進制數21對應的二進制數中,為1的最高位只能是權值為24的那一位,即二進制數從右往左數的第5位。不然,如果21對應的二進制數中,為1的最高位是權值為25的那一位或更高的數據位,此時即使其它的數據位全部取0,該二進制數表示的數據也至少是25=32,所表示的數據都比21大。相反,如果21對應的二進制數中,為1的最高位是權值為23的那一位或更低的數據位,此時即使其它的數據位全部取1,該二進制數表示的數據也一定比24小,因為20+21+22+23<24,即此時表示的數據一定比21小。

由于已經確定了十進制數21對應的二進制數,為1的最高位在權值為24的那一位,因此:

此時即可快速地確定十進制數21對應的二進制數為:(10101)2。因為23=8,顯然這位只能取0不能為1,不然即使其它位全部為0,此時24+23=24也大于21。同樣地,由于22=4,顯然這位只能取1不能為0,不然即使其它位全部為1,此時24+21+20=24+<24+22也小于21。其它各位依此道理,可以快速確定。

二進制數的各位權值即為2的各次冪方,以16位二進制數為例,即:

21521421321221121029282726252423222120

32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1

按以上方法,0～65535之間的任意十進制整數,即可快速地轉移為二進制數。比如:將十進制整數4097轉換為二進制整數,由二進制數的各位權值即可知道:此時為1的最高位只能在212位,從211位到21位均只能為0,不然這中間任何一位為1,其表示的數均超過4097了,而20位必須為1,否則就不夠4097。因此,十進制數4097對應的二進制數為:(1000000000001)2。

再比如:將十進制整數456轉換為二進制整數,根據以上轉換方法,可快速地寫出其二進制數為:(111001000)2。

5 結語

計算機馮諾依曼原理的核心思想之一就是計算機中的所有信息與數據都是二進制。因此,如何將人類使用的十進制數據轉換為計算機使用的二進制數據,是計算機領域的一個重要問題。十進制整數轉換為二進制整數的經典方法就是“除基倒取余”,數據較大時既不方便又容易出錯。本文基于二進制整數各位的權值滿足超遞增序列的特有屬,并結合“二進制數的數符只有0和1兩種情況,每一位數符對整個數據的貢獻或者就是該位的權值,或者對整個數據沒有任何貢獻”的關系,提出了一種十進制整數轉換為二進制整數的快速方法。文中也應用該方法給出了一些具體的轉換實例,結果表明:該轉換方法,比經典的“除基倒取余”轉換方法更簡單高效,當數據規模較大時,效果尤為明顯。

[1] 石元聆.進制轉換教學設計[J].計算機時代,2015(11):96-97. SHI Yuanling. Design of number system conversion teaching[J]. Computer Era,2015(11):96-97.

[2] 陳嘉勇,張衛明,胡金龍,等.一種最優(k,p)進制轉換算法[J].應用科學學報,2013,31(6):569-578. CHEN Jiayong, ZHANG Weiming, HU Jinlong, et al. An Efficient (k,p) Notational System Transform Algorithm[J]. Journal of Applied Sciences,2013,31(6):569-578.

[3] 顧沈明,張建科,崔振東,等.計算機基礎[M].第三版.北京:清華大學出版社,2014. GU Shenming, ZHANG Jianke, CUI Zhendong, et al. Basis of Computer[M]. Third Edition. Beijing: Tsinghua University Press,2014.

[4] 劉益.基于“權”和“基”的任意進制轉換[J].成都航空職業技術學院學報,2010,26(3):57-58. LIU Yi. Arbitrary Hexadecimal Conversion Based on Weight and Radix[J]. Journal of Chengdu Aeronautic Vocational and Technical College,2010,26(3):57-58.

[5] 劉均,李人厚,鄭慶華.一種基于進制轉換的數值型關聯規則分析方法[J].計算機工程,2005,31(9):17-18. LIU Jun, LI Renhou, ZHENG Qinghua. A Method for Quantitative Association Rule Mining Based on Decimal-binary Conversion[J]. Computer Engineering,2005,31(9):17-18.

[6] 趙建強.用多位數動態數組實現進制轉換的研究[J].湖南文理學院學報(自然科學版),2011,23(1):71-73. ZHAO Jianqiang. Research on realizing the system conversion by long number dynamic array[J]. Journal of Hunan University of Arts and Science(Natural Science Edition),2011,23(1):71-73.

[7] 劉建波,蔡文水,呂鐵山.十進制與任意進制轉換的設計與實現[J].計算機系統應用,2003(10):69-71. LIU Jianbo, CAN Wenshui. The Design and Implementation of Conversion Between Decimal Representation and N-Scale Notation[J]. Applications of The Computer Systems,2003(10):69-71.

[8] 林蔭,柴瑋.C語言的進制轉換分析[J].當代教育實踐與教學研究,2015(9):20-21. LIN Yin, CHAI Wei. Analysis of number base conversion in C language[J]. Contemporary Education Research and Teaching Practice,2015(9):20-21.

[9] 屠新兵.C語言中進制轉換的編程方法[J].電腦知識與技術,2015,11(29):124-125. TU Xinbing. Programming method for number base conversion in C language[J]. Computer Knowledge and Technology,2015,11(29):124-125.

[10] 顏慧.任意精度的十進制與N進制之間的轉換算法[J].福建電腦,2016(6):139-140. YAN Hui. Conversion algorithm between decimal and the base N with arbitrary precision[J]. Fujian Computer,2016(6):139-140.

[11] 曾美華.使用“8421”法輕松進行數制轉換[J].黑龍江科技信息,2015(31):108-108. ZENG Meihua. The use of "8421" for easy conversion between different base[J]. Heilongjiang Science and Technology Information,2015(31):108-108.

[12] 崔方送,程國忠,潘大志.以十進制為中心的進制轉換算法的設計與實現[J].電腦開發與應用,2012,25(3):66-68. CUI Fangsong, CHEN Guozhong, PAN Dazhi. Design and Implementation of Numeral System Conversion Based on Decimal[J]. Computer Development & Applications,2012,25(3):66-68.

[13] 羅國明,鐘晴江.基于歸類教學的進制轉換算法研究[J].計算機時代,2012(5):45-46. LUO Guoming, ZHONG Qingjiang. Digital conversion algorithm research based on classified teaching[J]. Computer Era,2012(5):45-46.

A Fast Method to Convert a Decimal Integer into A Binary Integer

LIU Shuo1PENG Lei2

(1. The First Senior High School of Jingmen City, Jingmen 448000) (2. School of Computer, China University of Geosciences, Wuhan 430074)

It is an important problem in computer field to convert a decimal data into a binary data used by the computers. The classic method to convert a decimal integer into a binary integer is inverting the remainder by dividing the base. However, the classic method is not convenient and easy to make mistakes when the data is large. Based on the unique attributes that the weight of each bit of the binary integer is a super increasing sequence and there are only 0 and 1 in the characters of the binary data, a fast method to convert a decimal integer into a binary integer is presented in this paper. Some examples of the conversion method are also given. The result shows that the new method is simpler and more efficient than the classic method, especially when the data is large.

decimal integer, binary integer, integer conversion, super increasing sequence

2016年8月3日,

2016年9月17日

國家自然科學基金(編號:41571403);中國博士后科學基金特別資助項目(編號:2012T50681)資助。

劉碩,女,研究方向:優化設計與數字工程。彭雷，男，博士，副教授，研究方向：優化設計，算法設計。

TP301

10.3969/j.issn.1672-9722.2017.02.024