CODEWITHSUNDEEP
cmathhexdecimalbigint
Newton's in-law
Newton's in-law

Reputation: 13

How can I convert a large decimal string to an equivalent hex string?

I am trying to implement a custom 1024 bit integer datatype in C. I want to implement operations like addition, subtraction and multiplication. Here is the structure I am defining:

typedef enum{POSITIVE, NEGATIVE} Sign;
typedef unsigned int uint32;

typedef struct int1024_tag {
    Sign sign;
    uint32* ints;
}bigInt;

Using this design allows me to efficiently store the integers in parts of 32 bits and operate on them efficiently.

However, as of now I need to input a hex string to initialize my bigInt variables. I want to know if there is a way to input a decimal string like char input2_dec[] = "8902384390968597266" and convert it into the string char input2_hex[] = "7B8B9F6FCDAA5B12" so that I can pass them to my currently defined functions.

I tried converting digit by digit. But that approach fails as it involves computation with big numbers - and it beats the whole purpose of defining my own datatype and writing code for big number computation from scratch.

Upvotes: 1

Views: 108

Answers (2)

chux
chux

Reputation: 153303

To parse a string in a wide integer:

  1. parse as unsigned char to use is...() functions.

  2. (optional) look for leading white-space.

  3. Look for a sign character.

  4. Look for digits.

  5. .. For each digit, scale the number by 10 and add the digit.

  6. .. Watch for overflow

  7. (optional) look for trailing white-space.

  8. Examine the end.

#include <ctype.h>
#include <stdbool.h>
#include <stdint.h>

typedef struct {
    uint32_t ints[1024/32];
    bool negsign;
} bigInt_alt;

bigInt_alt bigInt_from_string(const char *s) {
  bigInt_alt y = { 0 };
  const unsigned char *us = (const unsigned char *) s;

  // Maybe toss leading whitespace
  while (isspace(*us)) {
    us++;
  }

  y.negsign = *us == '-';
  if (y.negsign || *us == '+') {
    us++;
  }

  if (!isdigit(*us)) {
    ;  // TBD handle no digits
  }

  while (isdigit(*us)) {
    unsigned carry = *us - '0';
    for (size_t i = 0; i < 1024/32; i++) {
      uint64_t acc = y.ints[i];
      acc = acc * 10 + carry;
      y.ints[i] = acc & 0xFFFFFFFF;
      carry = (unsigned) (acc >> 32);
    }
    if (carry) {
      ; // TBD handle overflow
    }
    us++;
  }

  // Maybe allow trailing whitespace
  while (isspace(*us)) {
    us++;
  }

  if (*us != '\0') {
    ;  // TBD handle junk input
  }

  return y;
}

Some unchecked template-like code that uses a fixed size integer array.

To do:

  1. Fill in the TBD code.

  2. Add a char **endptr to record where parsing stopped, just like strtol().

  3. Add a base to parse base 16, 2, etc., just like strtol().

  4. For such wide input, consider allowing thousands separators ',' or the like.

Upvotes: 1

dbush
dbush

Reputation: 223689

Rather than convert the decimal string to a hex string, you can convert the decimal string directly.

Presumably you have a function that can convert an int into a bigint with one "digit". You can use this to convert individual decimal digits, then perform a multiply-by-10 and add loop for each digit.

Psedocode:

bigInt result = bigint_0;
char *p = input;
while (p) {
    int value = *p - '0';
    bigInt digit = new_bigint(value);
    result = bigint_add(bigint_mult(result, bigint_10), digit);
    p++;
}

Upvotes: 1

Related Questions