如何將二進制整數解釋爲三元數（基數3）？

Question

我的CPU寄存器包含一個二進制整數0101，等於十進制數5：

0101（4 + 1 = 5）

我想要的寄存器包含代替相等的二進制整數爲十進制10，如如果原來的二進制數0101是三元（基座3）和每個數字恰好是0或1：

0101（9 + 1 = 10）

我怎樣才能做到這一點現代CPU或GPU上1.最少的內存讀取和2.最少的硬件指令？

Answer 1

使用累加器。 C-ISH僞代碼：

var accumulator = 0 
foreach digit in string 
    accumulator = accumulator * 3 + (digit - '0') 
return accumulator 

要通過3加快乘法，可以使用（（蓄電池< < 1）+蓄電池），但一個好的編譯器將能爲你做的。

如果大部分數字都在相對較小的範圍內，還可以預生成查找表以使base2瞬時轉換爲base3（使用base2值作爲索引）。您還可以使用查找表來加速查找前N位數字，因此您只需支付其餘數字的轉換費用。

Answer 2

此C程序將做到這一點：

#include <stdio.h> 

main() 
{ 
int binary = 5000; //Example 
int ternary = 0; 
int po3 = 1; 

do 
    { 
    ternary += (binary & 1) * po3; 
    po3 *= 3;  
    } 
while (binary >>= 1 != 0); 

printf("%d\n",ternary); 
} 

環路編譯成本機代碼我的32位Intel機器上：

do 
    { 
    ternary += (binary & 1) * po3; 
0041BB33 mov   eax,dword ptr [binary] 
0041BB36 and   eax,1 
0041BB39 imul  eax,dword ptr [po3] 
0041BB3D add   eax,dword ptr [ternary] 
0041BB40 mov   dword ptr [ternary],eax 
    po3 *= 3;  
0041BB43 mov   eax,dword ptr [po3] 
0041BB46 imul  eax,eax,3 
0041BB49 mov   dword ptr [po3],eax 
    } 
while (binary >>= 1 != 0); 
0041BB4C mov   eax,dword ptr [binary] 
0041BB4F sar   eax,1 
0041BB51 mov   dword ptr [binary],eax 
0041BB54 jne   main+33h (41BB33h) 

對於示例值（十進制5000 =二進制1001110001000 ），它產生的三元值是559899.