Перевод в двоичную систему счисления НУ ОЧЕНЬ ДЛИННОГО ЧИСЛА

Question

Возник сложный вопрос: как переводить в двоичную счисления ну оооочень длинные числа, например, длиной в 255 знаков? Подскажите, пожалуйста, как это сделать? Написал функцию, которая переводит обычные числа в двоичную систему, но хотелось бы, чтобы она принимала массив char и возвращала массив char.


void dec2bin(int number)
{
    char m[255];
    int k = 0;
    while (number)
    {
        m[k] = (number % 2) + '0';
        k += 1;
        number /= 2;
    }
    k--;
    for (int i = k; i >= 0; i--) {
        std::cout << m[i];
    }
}

Answer 1

Написал что-то вроде такого. Производятся операции умножения, сдвига, прибавления непосредственно над вектором целых чисел.

#include <iostream>
#include <string>
#include <vector>
#include <bits/stdc++.h>

class BigInteger {
private:
    std::vector<uint32_t> number;

    void addBinary(const std::vector<uint32_t>&bin) {
        // in our case number is longer than bin
        bool carry = false;
        int j = 0;
        for(; j < bin.size(); j++) {
            number[j] += bin[j] + carry;
            if (number[j] & 0x80000000) {
                carry = true;
                number[j] &= 0x7fffffff;
            } else {
                carry = false;
            }
        }

        if (carry) {
            for(int i = j; i < number.size(); i++) {
                number[i] += carry; 
                if (number[i] & 0x80000000) {
                    carry = true;
                    number[i] &= 0x7fffffff;
                } else {
                    carry = false;
                    break;
                }
            }

            if (carry) {
                number.push_back(1);
            }
        }

    }

    void shiftLeftBinary(std::vector<uint32_t>&bin, int places) {
        bool carry = false;
        for (int j=0; j < places; j++) {
            for (int i=0; i < bin.size(); i++) {
                bin[i] <<= 1;
                bin[i] += carry;
                if (bin[i] & 0x80000000) {
                    bin[i] &= 0x7fffffff;
                    carry = true;
                } else {
                    carry = false;
                }
            }
            if (carry) {
                bin.push_back(1);
                carry = false;
            }
        }
        
    }

    void mult10() {
        std::vector<uint32_t> m = number;
        shiftLeftBinary(number, 3);
        shiftLeftBinary(m, 1);
        addBinary(m);
    }

    void addDigit(char c) {
        c = c & 0xf;
        uint32_t i = (int32_t)c;
        if (i > 9) i = 0;

        std::vector<uint32_t>v = {i};
        addBinary(v);
    }

public:
    BigInteger() {
        number.push_back(0);
    }

    void setDecimal(std::string& s) {

        number.clear();
        number.push_back(0);

        for(int i = 0;i < s.size(); i++) {
            this->mult10();
            this->addDigit(s[i]);
        }
    }

    std::string toString() {
        std::string s = "";
        uint32_t current;

        int j = 0;
        for(; j < number.size()-1; j++) {
            current = number[j];
            for (int i = 0; i < 31; i++){
                s += (current & 1) ? "1" : "0";
                current >>= 1;
            }
        }

        current = number[j];
        while(current){
            s += (current & 1) ? "1" : "0";
            current >>= 1;
        }

        std::reverse(s.begin(), s.end());
        return s;
    }
};

/////////////////////////////////////////

int main() {
    std::string s = "2218";
    BigInteger bigI;

    bigI.setDecimal(s);
    std::cout << s << std::endl;
    std::cout << bigI.toString() << std::endl;
    std::cout << std::endl;

    s = "9999999999";
    bigI.setDecimal(s);
    std::cout << s << std::endl;
    std::cout << bigI.toString() << std::endl;
    std::cout << std::endl;
}

https://github.com/tigertv/BeeNum

Answer 2

Заморочился, вроде работает)

#include <cstdlib>
#include <string>
#include <iostream>
#include <cassert>

using namespace std;

string divmod(const string &input, const int n, int &mod) {
    assert(n > 1);
    string res;
    string divided;

    for (auto c: input) {
        divided += c;
        auto r = div(stoi(divided), n);
        if (r.quot != 0) {
            res += (r.quot + '0');
        } else if (res.length()) res += '0'; // skip leading 0

        divided = to_string(r.rem);
    }

    mod = stoi(divided);
    return res;
}

string dec2n(string input, const int n) {
    // alphabet is 0..9a..zA..Z
    assert(n <= 62 && n > 1);
    string res;
    int mod;
    while (input.length()) {
        input = divmod(input, n, mod);
        res = (char)(mod + (mod < 10 ? '0' : (mod < 36 ?'a'-10:'A'-36))) + res;
    }

    return res;
}

int main(int argc, char const *argv[])
{
    int mod = 0;
    { auto d = divmod("10000000000000000000000000001", 2, mod); cout << d << ", " << mod << endl; }
    { auto d = divmod("22222222222222222222222222222", 2, mod); cout << d << ", " << mod << endl; }
    { auto d = divmod("82734682736482638476238476237", 2, mod); cout << d << ", " << mod << endl; }
    { auto d = dec2n("82734682736482638476238476237", 2); cout << d << endl; }
    { auto d = dec2n("1120175546223060130598879262554599764676229330351202023251910795166237121851795753689981066816411931661406295196294425474326181163776482575744054010948427561942575245782787742816421059855869212856715454123140043866392208776553004037021851895189704871507624871254033251309082668594716363388202777292967624069500740955581776209433563237536482725004063297910761839642728715573454854615414489086732463316913397879117051391977140598698313669359648529491927340819656031084171447299111728694528002", 3); cout << d << endl; } // 3 ** 1025 - 3 ** 512
    { auto d = dec2n("1032", 2); cout << d << endl; }
    { auto d = dec2n("42535295865117307932921825928971026433", 2); cout << d << endl; }
    { auto d = dec2n("359538626972463181545861038157804946723595395788461314546860162315465351611001926265416954644815072042240227759742786715317579537628833244985694861278948248755535786849730970552604439202492188238906165904170011537676301364684925762947826221081654474326701021369172596479894491876959432609670712659248448274433", 2); cout << d << endl; }
    { auto d = dec2n("295990750022427673183926996510285089534", 16); cout << d << endl; } // deadbeaffeedd00d000000000dadcafe
    { auto d = dec2n("1050215907863349821", 62); cout << d << endl; } // 1fA0000000Z

    return 0;
}

Answer 3

Пссст, как насчет попробовать немножечко буста:

#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

int main(int argc, char* argv[]) {
    const std::string str = "1120175546223060130598879262554599764676229330351202023251910729";
    export_bits(boost::multiprecision::cpp_int(str), std::ostream_iterator<int>(std::cout), 1);
}

Рабочий код

БЛОГ НА HUSL

Перевод в двоичную систему счисления НУ ОЧЕНЬ ДЛИННОГО ЧИСЛА

Ответы (3 шт):