除以二
在數學中，除以二是一種運算動作，即被除數的除數（分母）是二、或乘以二分之一的動作，又可稱為半分（dimidiation）或平分（halving）[1]。最早將除以二視為一種獨立運算的是古埃及人，其用於古埃及乘法演算法中的一個基本步驟[2]。一直到近代，除以二都有被單獨當作為一種運算方式看待的情況[3][4]。而在現代電腦程式設計中，由於大部分的情況下，除以二可以使用邏輯位移運算取代，因此也用於編譯器最佳化的技術中[5]。
歷史
編輯將除以二視為一個特殊的運算方式來處理乘法及除法的做法，最早可以追溯到古埃及人，其將除以二作為古埃及乘法演算法中的一個基本步驟[2]。 一直到十六世紀，仍有一些數學家將除以二視為一個獨立的運算方式[3][4]。 而在十進制算術、計算機科學的二進制及其他偶數進制算術中，除以二的計算相較於被除數的除數為其他數的除法而言，相對簡單，因此在現代的電腦程式設計中，除以二也會被視為一個獨立的運算子[5]。
二進制
編輯
在二進制算術中，除以二可以透過移位運算中的右移運算子來完成，即將二進位數中的每一位全部都向右移動一位，此技術應用於編譯器最佳化中的強度折減技術[6]。例如將105除以二，先將105表示為二進制，即1101001，接着將所有位元向右移一位，溢位的部分1被捨棄，即得到商110100，對應的十進制數值為52。類似地，此操作可以套用到所有除以二的正整數次方的情形，當被除數的除數（分母）為 時，其做法為將該數的所有位數右移 位來完成，例如欲將二十四除以八，24在二進制中計為11000，而8為2的三次冪，將11000向右位移3位得11，十進制為3，則得到商為3，即完成 的運算。由於位移運算通常比除法來得快，因此以這種透過位移運算取代部分除法運用在編譯器最佳化中是有幫助的[5]。但是，出於程式碼的可移植性和可讀性的考慮，通常仍然會在程式碼中以除法表示，替換為移位運算應由編譯器來完成[7]。不過，在有符號數處理中，上述做法並不能確保總是正確。一般邏輯右移一位可以將該數除以二，若除不盡總是會向下取整，但在某些程式語言中，有符號二進制整數的除法會向0捨入，也就是說，若一整數是負的，除不盡的狀況將會向上取整。
除以2k
編輯
邏輯右移可以處理除數（或分母）為任意二的冪的除法，即除以 。例如除以四、除以八等。更一般地，在特定底數 的進位制中，除數（或分母）為任意 的除法（k為整數）皆可以透過將數字位數向右移k位來完成。例如除以十，由於普遍的數字計法是透過十進制表達，因此可以直接將數字位數向右移1位來完成除以十的操作。例如230除以十，將230向右移一位，得23，即 。
二進制浮點數
編輯在二進制浮點數算術中，在不要求結果不為非正規化數的情況下，由於其是由二進制表示，因此可透過將浮點數科學記號的指數部分減一來完成除以二的動作[8]。許多程式語言會單獨專門為浮點數提供除以二的冪之函數，例如Java有提供一個名為java.lang.Math.scalb的函數來計算二的冪之比[9]；而C語言也有類似功能的函數，例如ldexp[10]。
十進制
編輯在十進制中，可透過下列演算法將任意整數除以二，其也可以作為定義底數為偶數之進位制中將任意數除以二的模型。其做法如下：
- 寫下整數N，並於左邊補上1個0。
- 針對N的每一個位數，根據下列表格寫下數字則可得到除以二的商。
| 第一位數為 | 偶數 | 偶數 | 偶數 | 偶數 | 偶數 | 奇數 | 奇數 | 奇數 | 奇數 | 奇數 |
|---|---|---|---|---|---|---|---|---|---|---|
| 下一位數 | 0 或 1 | 2 或 3 | 4 或 5 | 6 或 7 | 8 或 9 | 0 或 1 | 2 或 3 | 4 或 5 | 6 或 7 | 8 或 9 |
| 寫下 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
例如： 1738除以2=?
- 寫下 01738。
- 01：偶數位數0後面跟着1，寫下0；
- 17：奇數位數1後面跟着7, 寫下8；
- 73：奇數位數7後面跟着3, 寫下6；
- 38：奇數位數3後面跟着8, 寫下9；
- 商為0869。
從示例中可以看出0是偶數。此外，若N的最後一位是奇數，則需再將0.5加到結果中。
奇偶性
編輯
其他用途
編輯除以二可以用於某些速算法，例如某數乘以五可以透過先將該數除以二再乘以十來完成[11]，例如25乘以五，首先將25除以2得12.5，再乘以10得到結果為125。
參見
編輯參考文獻
編輯- ^ Steele, Robert, The Earliest arithmetics in English, Early English Text Society 118, Oxford University Press: 82, 1922.
- ^ 2.0 2.1 Chabert, Jean-Luc; Barbin, Évelyne, A history of algorithms: from the pebble to the microchip, Springer-Verlag: 16, 1999, ISBN 978-3-540-63369-3.
- ^ 3.0 3.1 Jackson, Lambert Lincoln, The educational significance of sixteenth century arithmetic from the point of view of the present time, Contributions to education 8, Columbia University: 76, 1906.
- ^ 4.0 4.1 Waters, E. G. R., A Fifteenth Century French Algorism from Liége, Isis, 1929, 12 (2): 194–236, JSTOR 224785, doi:10.1086/346408.
- ^ 5.0 5.1 5.2 Wadleigh, Kevin R.; Crawford, Isom L., Software optimization for high-performance computing, Prentice Hall: 92, 2000, ISBN 978-0-13-017008-8.
- ^ Granlund, Torbjörn; Peter L. Montgomery. Division by Invariant Integers Using Multiplication (PDF). [2019-04-22]. （原始內容存檔 (PDF)於2019-06-06）.
- ^ Hook, Brian, Write portable code: an introduction to developing software for multiple platforms, No Starch Press: 133, 2005, ISBN 978-1-59327-056-8.
- ^ Computer Architecture and Organization: Design Principles and Applications. Tata McGraw-Hill. 2004: 170 [2019-04-23]. ISBN 9780070532366. （原始內容存檔於2019-08-18）.
- ^ Math.scalb. Java Platform Standard Ed. 6. [2009-10-11]. （原始內容存檔於2009-08-29）.
- ^ Programming languages — C, International Standard ISO/IEC 9899:1999, Section 7.12.6.6.
- ^ 优等生必学的速算技巧大全. 清華大學出版社. 2018 [2019-04-24]. ISBN 9787302463214. （原始內容存檔於2019-08-18）.