SORU
6 Kasım 2008, PERŞEMBE


Nasıl C büyük int uygulamak

Programlama bir egzersiz olarak C büyük int bir sınıf uygulamak istiyorum. İşleyebilir bir sınıf daha büyük, uzun bir int sonra numaraları. Orada birçok açık kaynak kodlu uygulamalar zaten var olduğunu biliyorum, ama benim kendi yazmak istiyorum. Doğru yaklaşım ne bir fikir almak için çalışıyorum.

Genel stratejinin bir dize numarasını almak, ve sonra daha küçük sayılar (örneğin tek basamaklı) kırmak olduğunu biliyorum, Ve bir dizi yerleştirin. Bu noktada nispeten basit çeşitli karşılaştırma operatörleri uygulamak gerekir. Benim asıl endişem ayrıca gibi şeyler uygulamak istiyorum nasıl ve çarpma.

Genel bir yaklaşım ve gerçek çalışma kod appose gibi tavsiyeler arıyorum.

CEVAP
6 Kasım 2008, PERŞEMBE


Eğlenceli bir meydan okuma. :)

Ben rasgele uzunlukta tamsayı istediğinizi varsayalım. Aşağıdaki yaklaşım öneriyorum

Veri türü ikili doğa"". int düşünün Bir şeyler eklemek basit ikili işlemler CPU devreleri ne taklit etmek için kullanmayı düşünüyor. Daha derinlemesine ilginizi çeker, this wikipedia article on half-adders and full-adders okuma düşünün. Buna benzer birşeyi yapıyor olacağım, ama o kadar düşük seviye olarak gidebilirsin, ama tembel olmak, sadece vazgeçmek ve daha basit bir çözüm bulabileceğimi düşündüm.

Ama ekleme, çarpma, çıkarma ile ilgili herhangi bir algoritmik detaylara girmeden önce, bazı veri yapısı bulalım. Basit bir şekilde, tabii ki, bir şeyler saklamak için std::vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Bunu önceden ayır eğer belirli bir boyutu, vektör yapmak istiyorsanız ve düşünebilirsiniz. Nedeni çeşitli işlemler için, vektörün her elemanı ile gitmek zorunda kalacak - O(n). - İlk bakışta ne kadar karmaşık bir işlem olacak bilmek isteyebilirsiniz ve sabit bir n tam da bunu yapar.

Ama şimdi bu sayılar üzerinde çalışan bazı algoritmalar için. Mantık düzeyinde, bunu yapabilirdi ama sonuçları hesaplamak için sihirli İŞLEMCİ gücü kullanacağız. Ama Yarım ve FullAdders mantık-şekil sonrasını biz hallederiz ne taşıdığı ile ilgilidir. Örnek olarak uygulamak istiyorum nasıl düşünün= operatörü. Büyük Tamsayı<^ için her numarayı . ::value_, bu ekleyin ve eğer sonuç taşımak çeşit üretir görmek istiyorum. Bit-wise yapmayacağız, ama bizim temel alınan tür doğası üzerine (uzun ya da int ya da kısa veya herneyse) kullanır: taşacaktır.

Eğer iki sayı eklerseniz, şüphesiz, sonuç bu numaraları daha büyük bir daha büyük olmalı, değil mi? Eğer değilse, o zaman sonucu taştı.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator  = (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count  )
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0   op1   carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0   op1   carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

Diğer aritmetik işlem benzer. Heck, stl-funktorlar std kullanabilirsiniz bile::artı ve std::eksi, std::times ve std::böler ... ama taşımak zihin. :) Sen de uygulamak çarpma ve bölme kullanarak sizin artı ve eksi operatörleri, ama çok yavaş, çünkü bu hesapla, sonuçları önceden hesaplanmış bir önceki aramalar için artı ve eksi her yineleme. Bu basit bir görev için, use wikipedia ya da web iyi algoritmalar vardır.

Ve tabii ki, gerekir uygulamak standart operatörler gibi operator<< (sadece shift her değeri value_ sol için n bit, başlamada value_.size()-1... oh, ve unutmayın!:), operator< - hatta en küçük burada, kontrol edilmesi zor basamak sayısı size() ilk. Ve benzeri. Sonra sınıf, befriendig std tarafından yararlı olun::başka operator<<.

Bu yaklaşım yararlı olur umarım!

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • knopik96

    knopik96

    7 Mayıs 2011
  • Crossover

    Crossover

    18 HAZİRAN 2007
  • tutvid

    tutvid

    19 AĞUSTOS 2006