Как интерпретировать двоичное целое число как троичное (основание 3)? - PullRequest
Новая
       35

Как интерпретировать двоичное целое число как троичное (основание 3)?

0 голосов
/ 25 февраля 2012

Мой регистр ЦП содержит двоичное целое число 0101, равное десятичному числу 5:

0101 (4 + 1 = 5)

Я хочу, чтобы регистр содержал вместо двоичногоцелое число равно десятичному 10, как если бы исходное двоичное число 0101 было троичным (основание 3), и каждая цифра оказалась либо 0, либо 1:

0101 (9 + 1 = 10)

Как я могу сделать это на современном CPU или GPU с 1. наименьшим количеством чтений памяти и 2. наименьшим количеством аппаратных инструкций?

Ответы [ 2 ]

2 голосов
/ 25 февраля 2012

Используйте аккумулятор. C-ish Псевдокод: 

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

Чтобы ускорить умножение на 3, вы можете использовать ((аккумулятор << 1) + аккумулятор), но хороший компилятор сможет сделать это за вас. </p>

Если большой процент ваших чисел находится в относительно небольшом диапазоне, вы также можете предварительно сгенерировать справочную таблицу, чтобы выполнить мгновенное преобразование из base2 в base3 (используя значение base2 в качестве индекса). Вы также можете использовать справочную таблицу для ускорения поиска первых N цифр, поэтому вы платите только за преобразование оставшихся цифр.

0 голосов
/ 26 февраля 2012

Эта программа на 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.

...