能否使用3的指數來減小二進位文件存儲的體積？

12-30

感謝認真回答的答主。後來我托關係找了個蘇州大學的研三數學系學生，他證明了不可行(雖然他證明得不嚴謹，但對這個問題我水平太低，不想考慮了)......具體看我的回答
有人提抽屜原理，我覺得不對，因為這不是一一對應的。有人提香農，我查了一下，這應該算是提高存儲密度，並不改變信息熵。
原問題：
計算機文件可以視為一個巨大的二進位數。現在考慮使用3的指數來表示文件。比如247是3的5次方+3+1，二進位為11110111，現在我想用101+1+01的形式存儲它，位數變少文件不就變小了么？(例子不好，但是這個意思，數字大的情況下3的指數增長速度比2快很多)
用數學形式來表達:一個非常大的二進位數（設有x位，x&>2^30），該二進位數可表示為(+-意思為可以加或者是減)3^a1+-3^a2+-3^a3+-......+-一個二進位數(位數為y)。問a1+a2+a3+....+y+kn-k(用於分割符和加減號的存儲，k值估計為2到16)與x的大小關係。有多少的可能性，前者比後者小。小的情況下，平均是後者的幾分之幾？

比較仔細地試圖以題主的角度來理解這個演算法，然後寫下了這個答案。

比如247是3的5次方+3+1，二進位為11110111，現在你想用101+1+01的形式存儲它。

1、如果這是個定長碼，每8位二進位一組映射的非奇異碼，結果至少是6組，最後這個儲存在計算機里應該是：

101 000 001 000 000 000

壓縮率225%。

而且還有的數據，沒辦法用這個演算法映射到這個定長空間，例如說242。

2、如果101+1+01表示成101101，這是變長碼，這個編碼方法不是唯一可解碼，編碼完沒辦法消歧，也沒辦法解碼。

——————————————————————————

關於另一位晶元行業從業者的高贊答案，目前使用最多的是四進位或者八進位的存儲器，各位可以檢查自己各類數碼設備的的存儲器。

基本上都是八進位的TLC顆粒的存儲器，或者是四進位的MLC顆粒存儲器。可能你會有七八個TLC或者MLC的存儲器，而二進位存儲器基本大部分人就最多持有那麼一兩個。

Q：這樣會縮小文件存儲的體積嗎？

A：當然會，多電平狀態的存儲晶元可以提高存儲密度。例如原來某文件，原來用MLC需要 $1cm^{3}$ 大小的存儲器才能儲存，現在換成同等生產工藝的TLC可能只需要 $0.3 cm^{3}$ 大小的存儲器就能儲存，體積大大減少。

然而——注意到了嗎？這裡用的文件存儲體積單位是 $cm^{3}$ ，這位答主以及他下面的點贊者，屬於混淆概念了。

我們平時用的文件存儲體積單位是什麼呢？是Bit（比特）。

最後讓我們回顧信息熵公式：

$H(U) = -sum_{i=1}^{n}{p_{i}log p_{i}}$

那麼大家可以自己計算，這位答主的進位轉換方法，真的讓文件存儲體積減小了嗎？

題主的思路是可以壓縮的。

看了好多的回答，很多人上來就先嘲諷題主一翻，都沒有看完題主的問題描述。根據題主的思路和演算法，確實可以把一個文件壓縮。。。。

但是！

這種壓縮演算法最大的問題是：不！能！解！壓！

話說，雖然題主的表達方式確實是錯的，在嘲笑題主的同時，但難道各位不知道3進位確實比2進位更節省存儲空間嗎？更接近e的進位是更節省空間的，顯然3比2更接近e，所以三進位節約空間是有道理的，只不過題主他看錯了方向。

1到100000這個範圍的正整數里，2進位更省空間的有8488個，3進位更省空間的有76226個，其餘15286個是占空間相等的情況。

當然了，三進位補碼很難看，估計會被人罵死。換了我，我也不喜歡用三進位，太反人類了。

-----------------------------------------

看來很多人還是沒明白，我再補充一些：

本來想自己算，但發現有人已經給算過了（zz from newsmth e進位是信息表示的最優解）：

假定總共有n位，每位m個狀態，m*n=v

在v一定時，使得m^n最大
也就是k(n)=(v/n)^n最大
考慮一般情況下
ln(k(n))=(ln(v)-ln(n))*n=ln(v)*n - ln(n)*n
對n求導 ln(v) - (n*1/n + ln(n)) = ln(v) - 1 - ln(n)
解得ln(n)=ln(v)-1是k(n)唯一的極值點
易知是k(n)最大值點
所以n=v/e m=e時，k(n)最大

所以數學上就可以證明三進位比二進位更省空間。

有人說二進位存儲器更便宜，那是因為現代計算機已經選擇了二進位，所以硬體製造商自然會尋找更廉價的二進位存儲設備，這是一個互相影響的過程。

不能，所有有關壓縮的問題請學習資訊理論，參考香農三大定理

簡單來說信息能壓縮到什麼程度完全只跟信源有關，以信源熵為限度（使用香農編碼），所以討論壓縮演算法永遠得先說出對信源的假設，否則沒有任何實際意義，因為如果是完全隨機分布的數據是不可能壓縮的

用三狀態存儲信息其實是可行的，但是這個不能叫壓縮，因為這並不改變信息熵，但是可以提高存儲密度，因為用同樣的器件保存了更多的信息。

現在的SSD就是這個乾的，最早的SLC是一個單元存儲1bit也就是2狀態，然後MLC改進為一個單元可以分成4個電平狀態也就是保存2bit，TLC則進一步達到8狀態3bit，後面還有更變態的QLC。好處么就是相同面積的SSD晶元容量得到了大幅的提升，壞處么就是晶元壽命大幅縮短

簡單說，如果想表達的數集在整數集上不是稀疏的，那麼由於計算機底層電路邏輯，n位二進位最多表示2^n個不同數（指連續的range），跟你上層採用的映射方法無關（抽屜原理）。

而上層採用二進位壓縮時取到了這個上確界，所以不管你採用多麼fancy的進位和小trick，都不會取得更好的壓縮效果。

是時候設計無窮大進位了

這樣就可以把任意信息壓縮到一個符號

香農，給，吃蘋果

Update 1: 題目現在這個表述的話

那其實是壓縮編碼...

壓縮的代價是解碼錶會變大...

和那個 $e$ 進位最優不是一回事...

Update 2: 說個題外話...

Code Golf...現在不堪入目

就是被這種破壓縮法搞的...

J語言,Befunge語言還算好的...

Jelly(Python),MATL(Matlab),Japt(JavaScript)這種什麼玩意兒...

一個巨大的編碼表,用UTF字元代替函數...

為了短而短,噁心死了...

壓縮不可能，信息量是恆定的……

不過對別的答案說電路只能有開閉兩種狀態的，其實歷史上是有過三進制計算機的，據說還能節約製造成本和降低能耗：

Ternary computer

Setun

當然對於現代大規模集成電路爲基礎的計算機而言，批量生產的規模更能節約成本……

你那個加號怎麼存儲的？別告訴我加號不佔存儲空間啊。

寫在紙上變短了不代表實際存儲的內容變短

1m和1000mm是一樣長的

蘇聯搞過三進位計算機，可以看看相關資料。

如果你的辦法可行，那用 16 進位豈不是更好？

但是 1 個 16 進位數字 = 4 個 bit，1 byte = 2 個 16 進位數字，其實一點都沒有壓縮。

資訊理論什麼的太理論了。我們就直觀感受下好了。

現在考慮使用3的指數來壓縮文件。比如247是3的5次方+3+1，二進位為11110111，現在我想用101+1+01的形式存儲它，位數變少文件不就變小了么？

那麼問題就來了。計算機中的數據都是以二進位存儲的，位元組是最基本的存儲單位。那麼 247 實際的表示是 11110111，1 個位元組。那麼你把它轉成 3 進位後為 $1(3^5)+0(3^4)+0(3^3)+0(3^2)+1(3^1)+1(3^0)$ ，即 100011。然後一個三進位位的範圍為 0-2，最少需要 2 個二進位位來存儲。所以你這個轉換之後的結果為 6 位，所以至少需要 6 * 2 等於 12 個二進位位來保存。咦，好像需要 2 個位元組，變多了嘛？？？恭喜題主發明了「膨脹」演算法。

我們來算一下吧。只考慮自然數的情況。任意自然數 $n$ ，用二進位表達需要 $log_2(n+1)$ 位，至少需要的位元組數為 $frac{1}{8}log_2(n+1)$ ，而其三進位表達需要 $log_3(n+1)$ 位，每一個三進位至少需要 2 個二進位位來表達，那麼需要的二進位位為 $2log_3(n+1)$ ，則位元組數為 $frac{2}{8}log_3(n+1)$ ，除以原來的位元組數，得 $frac{2log_3(n+1)}{log_2(n+1)}approx1.2618595071429148$ ，你還說你這不是「膨脹」演算法？

雖然回答晚了但還是想說兩句。

題主其實說了兩種概念。

1。平時用二進位現在換成三進位。

2。只儲存set位的序號。

第一點，如果底下硬體還是二進位儲存的話，沒有意義的，三進位到二進位反而有損耗，不解釋。

第二點，這算是一種編碼方式。平時我們的數據是把每一位都用01來表示是否set，而如果set的位很少，理論上是有利可圖的，但這與幾進位無關。

比如十進位的10億，即1000000000，也可以表示為19，即第9位為1。或者按照題主的寫法就是9（即10^9，20億為99，10^9+10^9，先不考慮減法）。

比如二進位里2^512範圍的數字，位數序號只有0~511，即2^10，這樣看10bit比512bit小很多，哪怕需要描述很多個位都有剩餘。可是512/10，即壓縮後的512bit只能描述完整的51個位，而原始數據卻有512個位呢。

當然也可以再壓縮一下，要求位序號從大到小，即出現了第128位set後，後續只可能是0~127，那就只需要8位來描述就行了。理論最大值其實就是從0開始遞增，計算長度和直到512bit，也就是sum((2^(i-1))*i)=512，也就是最多能表示90個位——還是比512位要小很多。

那麼把1、2兩種辦法都用上呢？

比如6，可以是3^1+3^1，即1，1（每個都需要很大的表示範圍）；或者是2*3^1，即2，1（前個值只需要1-2的表示範圍）。後者看起來的確容易省，但1-2的表示範圍用上三進位的一個位（0-2）還是浪費了。不過0-1剛好可以塞進二進位里的一個bit，此時三進位轉回二進位反倒能省一點空間。

2^512大致是3^323。前面求得二進位里512bit能最多塞進90個位序號，現在每個數字還要跟上一個bit用於1/2，即能塞進的位更少了，大概最多能放80個位序號，相比323的需求還是不夠。

引入減法的話，相當於把某一位翻轉，0-&>1或者三進位里0-&>2。這樣一來理想條件下可以使得編碼數字里只有一半的位為set，但隨之而來的是每個位的表示範圍要翻倍（1-2變成-1，-2，1，2，剛好需要二進位里的兩個bit），所以是沒有變化的。

那麼為什麼會沒有效果呢？

0x73是10000011b，但其實他不止利用了0/1的信息，還通過隱含的位置關係來表達信息，所以利用率高。

而記錄set位序號的話，前面的set位是7，1，0；可以表示為710/701/170/107等等，位置改變不影響數據結果——看到了吧，位置信息沒有用上，自然利用率低。強制從大到小排列也只是稍微利用了位置信息，利用率自然還是不夠高。

綜上所述，只有在特定情況下能達到壓縮的效果。

現代計算機之所以採用二進位，是因為數字半導體晶體管（TTL或MOS）在導通和截至兩個狀態的輸出電平最穩定。

比如，晶體管處於截止態，輸出管腳5V高電平，表示1；

晶體管處於導通態，輸出管腳0V低電平，表示0。

那晶體管有沒有介於導通與截止之間的中間態呢？

是有的，不然怎麼叫半導體呢，這個叫線性放大態。

理想化的輸出函數是這樣的（Vi為輸入電平，Vo為輸出電平）：

Vo = 0V （-∞ &< Vi &<0V）——截止態

Vo = k*Vi（0 &< Vi &< 5V）——線性放大態

Vo = 5V (5V &< Vi &<∞) —— 飽和導通態

其中模擬電路的器件是工作在線性放大態；

數字電路器件是工作在截止與飽和態，這樣根據電平的高低來判斷最准也為穩定。

因此邏輯電路（與門、或門、與非門等）都只用高或低電平來表示不同狀態，進而演化成1/0兩種數字表達。

那麼，是不是能找到有N個穩定狀態半導體器件就能使用N進位呢？

答案是的，就是量子計算機。

一個量子有N個疊加態，那麼一個量子就可以表示N進位的一位。

10個量子就能表示（N^10-1）範圍內的數字。

這個不能算壓縮，不過題主的想法也算是一個很工程向的想法，如果表示一位三進位的存儲單元和二進位的造價一樣，而且很容易造出相同規模的器件來，那成本就被這個壓縮演算法壓縮了（逃

你並沒有進行任何壓縮。

我先試圖理解一下題意哈

題主並不打算用任何三進位的硬體，而單純只是想要用二進位儲存一個數字拆分成3的冪次之後的指數們，現在題主想知道，通過這種換算能不能讓儲存數據消耗的bit數少一點。

答案是：可以，但是會損失可表示數的範圍

因為n-bit （n個0或1）的系統最多只能表示2^n種狀態，給一個狀態分配一個數字的話，就只能表示2^n個數字。無論你用的是什麼分配方法：直接對應2進位數字也好，把最高位當做符號位來表示負數也好（順便此處有1"s complement和2"s complement 兩種分配方案），用奇怪的三進位演算法來算出對應的數字也好（也就是題主的想法），甚至列一張亂七八糟的超級長的一一對應的表格來規定10110110對應數字0，00001011對應數字1………也好。

它都只能表示2^n個數字

然後我們再來看看題主的想法，或者，更一般化一點的表述：能否構造一種一一對應，使得表達一個數需要的bits更少？

當然可以啦，你看啊，本來5要用00000101來表達，但是我用一套新的方法就只要用101來表達就夠了呢！（滑稽）

還有更神奇的呢，我設計一種對應方案，使得二進位1對應數字5，二進位0對應數字6，這樣就只要一個bit就能表示5了！（滑

而且只要用10也就是兩個bits就能表示數字56了！（氵）

可是……57呢？58呢？壓縮了01串的長度必然會使得整個系統可以表示的狀態數變少，從而導致某些數字變得不可表示。

所以，無論題主構造了多精妙多有數學關係的一一對應。從你想要用7個bits表示247開始，你的自然數序列里就有了缺口。你的方法就不再能從0一個一個數到256。最後導致你的方案在實踐中失去意義：沒有人會想要在只有5和6的數學裡做加減乘除的

題主，你確定你設計的是「壓縮」而不是「密碼」？

結論是不能。

例如題目中說的一個x位的二進位數等於一個y位的三進位數，其中y &< x。

問題在於，你要使用多大的內存空間來表示一個三進位位呢？

一個x位的二進位數所佔用的精確內存是x bit。實際佔用會稍多一些，但是在這裡我們先不考慮多佔用的那部分。

一個y位的三進位數所佔用的精確內存是多少bit呢？

顯然你不可能用1個二進位bit去表示1個三進位位，因為三進位的2無法用單一的二進位位表示。

那麼至少要用到2個二進位bit去表示1個三進位位。所以實際上一個y位的三進位數至少佔用的精確內存空間就是2*y個二進位比特。

而2*y &> x是顯然的。

另外，用2個二進位位去表示一個三進位位是不合算的。因為2個二進位位可以最多可以表示4個數，也就是可以當作一個四進位位使用。在使用三進位位的時候有一位是浪費的。

那麼使用四進位進行壓縮可不可行呢？

顯然是不可行的。因為兩個二進位位和一個四進位位是精確對應的，根本就沒有壓縮。

如果題主還聽不懂，我就沒有辦法了。