Sayısal sistem arasındaki dönüşüm için verimli algoritma

Kaynak tamsayı büyüklüğü rasgele olduğunda sayı sistemi arasında dönüştürme için verimli bir algoritma var mı? Örneğin, giriş olarak ondalık biçiminde 148 olan bir tamsayı dizisi {1, 4, 8} olduğunu varsayalım. Onaltılık biçimde {9, 4} veya sekizlik olarak {2, 2, 4} veya ikili biçimde {1, 0, 0, 1, 0, 1, 0, 0} şeklinde veya yalnızca { 148} 1234-ary formatında veya bir şey.Sayısal sistem arasındaki dönüşüm için verimli algoritma

Gerçek değer, makine tarafından desteklenen kelime boyutunda ifade edildiğinde basittir. Ama keyfi boyuta geldiğinde, O (n^2) 'den daha verimli bir yol bulamıyorum. baz ile

kaynak

2010-08-23 summerlight

O (n) de mümkün olmalıdır. Math.stackexchange.com üzerinde denemek isteyebilirsiniz. –

Böl, 0

Bu nedenle, örneğin 16

148/16 = 9 r 4 
    9/16 = 0 r 9

Böylece tabanında 148 dönüştürmek = modül geri itin yıkayın ve! bölüm ise, tekrar hex 148 0x94 olan . Bu çok uzun sürmemeli.

kaynak

2010-08-23 08:53:03

Ne yazık ki, bir sayı yeterince büyük olduğunda bu kadar basit değil - mevcut bilgisayar mimarisinde 1 atomik tamsayıda temsil edilemeyen 10^100'ü düşünün. – summerlight

Elbette, big_int sınıfı gibi bazı soyutlamalar kullanılabilir, ancak bu problemi daha da kötüleştirir, çünkü modüler ve bölünme işleminin zaman karmaşıklığı O (n^2) ve O (n) modüler ve bölme işlemine ihtiyaç duyarız. dönüştürme. – summerlight

Sayısal sistem arasındaki dönüşüm için verimli algoritma

cevap

İlgili konular