Как перейти с шестнадцатеричной системы на 2 ^ 16 в c ++

Question

У меня есть такая задача: пользователь вводит числа N1 (str1) и N2 (str2) в шестнадцатеричном формате. Программа должна преобразовать числа из шестнадцатеричной системы в систему 2 ^ 16 и посчитать сумму чисел N1 и N2 в системе 2 ^ 16, а затем преобразовать результат в шестнадцатеричную систему.

У меня было такоеИдея: сначала преобразовать из шестнадцатеричного в десятичное (я могу сделать это). Затем возьмите каждое число по модулю 2 ^ 16 логарифмом основания 2 ^ 16 числа раз N1dec (dec11) (или N2dec (dec22)) и запишите остатки в соответствующие массивы. Это где мои проблемы начались. Мое преобразование из десятичной в 2 ^ 16 система не работает. Надеюсь, что вы можете помочь.

#include <iostream> 
using namespace std;

int main()
{
//HEX to decimal
const char* const str1 = "101D0";//7A120 = 500000; 101D0 = 66000;   //1F4 = 500=dec1=N1
cout << "Hello!\nFirst number in HEX system is " << str1 << endl;
istringstream is(str1);
int dec1;
is >> hex >> dec1;
if (!is && !is.eof()) throw "dammit!";
cout << "First number in decimal system: " << dec1 << endl;
const char* const str2 = "1567";//5479=dec2=num2
cout << "Second number in HEX system is " << str2 << endl;
istringstream iss(str2);
int dec2;
iss >> hex >> dec2;
if (!iss && !iss.eof()) throw "dammit!";
cout << "Second number in decimal system: " << dec2 << endl;
//

//Decimal to 2^16 system
int dec11 = dec1;//because dec11 will be = 0
int dec22 = dec2;//because dec22 will be = 0

int k = 1 << 16;
cout << "2^16 = " << k << endl;
int intPART1 = log(dec11) / log(k);
cout << "Int part of log2^16 (" << dec11 << ") is " << intPART1 << endl << "So num1 in 2^16 system will look like ";

int *n1 = new int[intPART1 + 1];
for (int i = 0; i <= intPART1; i++)
{
    if (i != 0)
    {
        n1[i] = dec11 % k*(1<<16-1);
        dec11 = dec11 / k;
    }
    else
    {
        n1[i] = dec11 % k;
        dec11 = dec11 / k;
    }
}
for (int i = intPART1; i >= 0; i--)
{
    cout << n1[i] << "   ";
}
cout << endl;
int intPART2 = log(dec22) / log(k);
cout << "Int part of log2^16 (" << dec22 << ") is " << intPART2 << endl << "So num2 in 2^16 system will look like ";

int *n2 = new int[intPART2 + 1];
for (int i = 0; i <= intPART2; i++)
{
    if (i != 0)
    {
        n2[i] = dec22 % k*(1 << 16 - 1);
        dec22 = dec22 / k;
    }
    else
    {
        n2[i] = dec22 % k;
        dec22 = dec22 / k;
    }
}

for (int i = intPART2; i >= 0; i--)
{
    cout << n2[i] << "   ";
}
cout << endl;

Answer 1

Поскольку шестнадцатеричные значения имеют основание 16, скажем, 16 ^ 1, а основание 2 ^ 16 можно пересчитать в 16 ^ 4, мы уже можем видеть, что ваша целевая база кратна вашей исходной базе. Это делает вычисления довольно простыми и понятными. Все, что нам нужно сделать, это немного сдвинуть бит.

int hexToInt(char c)
{
    if (c >= 'a')
        return c - 'a' + 10;
    if (c >= 'A')
        return c - 'A' + 10;
    return c - '0';
}

// Converts hex to base 2^16. vector[0] holds the MSB.
std::vector<unsigned short> toBase0x10000(std::string const& hex)
{
    std::size_t bufSize = hex.size() / 4 + (hex.size() % 4 > 0);
    std::vector<unsigned short> number(bufSize);

    int shift = 0;
    int value = 0;
    std::size_t numIndex = number.size();

    for (int i = hex.size() - 1; i >= 0; i--)
    {
        value |= hexToInt(hex[i]) << shift;
        shift += 4;

        if (shift == 16)
        {            
            number[--numIndex] = static_cast<unsigned short>(value);
            shift = 0;
            value = 0;
        }
    }

    if (value != 0)
        number[--numIndex] = static_cast<unsigned short>(value);

    return number;
}

std::string fromBase0x10000(std::vector<unsigned short> const& num)
{
    std::stringstream ss;
    for (auto&& digit : num)
        ss << std::hex << digit;
    return ss.str();
}

toBase0x10000 возвращает std::vector<unsigned short>, поэтому каждый элемент в векторе представляет одну цифру вашего базового числа 2 ^ 16 (поскольку unsigned short может содержатькроме этого диапазона значений).

В качестве побочного эффекта эта реализация поддерживает любое число точности, поэтому вы не ограничены диапазоном значений числовых типов, таких как int или long.

Здесь - полный пример.

Answer 2

Поскольку это похоже на учебное упражнение, которое вы хотите решить самостоятельно, вот два совета:

Шестнадцатеричная цифра представляет четыре бита, поэтому каждая базовая цифра - 65 536 состоит из четырех шестнадцатеричных цифр. Поэтому вы можете читать цифры в группах по четыре, без необходимости преобразования в или из десятичного числа. Тот же алгоритм, который вы узнали для декодирования четырех десятичных цифр, будет работать для шестнадцатеричного числа, за исключением того, что умножения будут еще более эффективными, поскольку компилятор оптимизирует их в инструкции сдвига влево.

Вы должны использовать тип uint16_t из<stdint.h> для этой арифметики, так как она точно правильного размера и без знака. Арифметическое переполнение без знака определяется как обтекание, что вам и нужно. Переполнение со знаком - неопределенное поведение. (Или #include <cstdint>, за которым следует using std::uint16_t;, если вы предпочитаете.)

Чтобы добавить цифры в любую базу b , возьмите сумму цифр по модулю b . Это будет еще проще, когда b имеет степень 2, потому что x86 и многие другие процессоры имеют 16-битную инструкцию добавления без знака, которая делает это аппаратно, и на любой машине, которая этого не делает,компилятор может оптимизировать это до битовой маски & 0xFFFFU.

В обоих случаях вы можете, если хотите, выписать двоичные оптимизации вручную, используя << и & вместо * и %. Это может даже немного улучшить сгенерированный код, если вы используете математику со знаком, а не без знака. Однако любой современный компилятор достаточно умен, чтобы выполнить такую ​​микрооптимизацию за вас. Вам лучше не оптимизировать преждевременно, а писать код, который легче читать и понимать.