3

このプログラムでは、基数 10 の 1 つの文字列として表現される任意の大きな符号なし整数の入力が必要です。出力は基数 16 の整数を表す別の文字列です。

たとえば、入力は「1234567890987654321234567890987654321234567890987654321」で、出力は「CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1」となります。

アルゴリズムが高速であるほど優れています。

入力が 32 ビットまたは 64 ビットの整数に制限されている場合は非常に簡単です。たとえば、次のコードは変換を実行できます。

#define MAX_BUFFER 16
char hex[] = "0123456789ABCDEF";

char* dec2hex(unsigned input) {
    char buff[MAX_BUFFER];
    int i = 0, j = 0;
    char* output;

    if (input == 0) {
        buff[0] = hex[0];
        i = 1;
    } else {
        while (input) {
            buff[i++] = hex[input % 16];
            input = input / 16;
        }
    }

    output = malloc((i + 1) * sizeof(char));
    if (!output) 
        return NULL;

    while (i > 0) {
        output[j++] = buff[--i];        
    }
    output[j] = '\0';

    return output;
}

本当に難しい部分は、「任意の大きな」符号なし整数です。私はグーグルで検索しましたが、それらのほとんどは 32 ビットまたは 64 ビット内での変換について話しています。運は見つかりません。

誰かがヒットまたは読むことができるリンクを与えることができますか?

前もって感謝します。

編集これは私が最近遭遇したインタビューの質問です. この問題を解決する方法を簡単に説明できる人はいますか? gmp ライブラリがあることは知っており、以前はそれを利用していました。ただし、インタビューの質問として、外部ライブラリを使用しない必要があります。

4

7 に答える 7

4

一連の数値を任意の基数から変換するために使用できる Python の簡単なソリューションについて説明する記事を書きました。私はもともとソリューションを C で実装していましたが、外部ライブラリへの依存は望んでいませんでした。非常に簡単な Python コードを C などで好きなように書き直すことができるはずです。

Python コードは次のとおりです。 

import math
import string

def incNumberByValue(digits, base, value):
   # The initial overflow is the 'value' to add to the number.
   overflow = value
   # Traverse list of digits in reverse order.
   for i in reversed(xrange(len(digits))):
      # If there is no overflow we can stop overflow propagation to next higher digit(s).
      if not overflow:
         return
      sum = digits[i] + overflow
      digits[i] = sum % base
      overflow = sum / base

def multNumberByValue(digits, base, value):
   overflow = 0
   # Traverse list of digits in reverse order.
   for i in reversed(xrange(len(digits))):
      tmp = (digits[i] * value) + overflow
      digits[i] = tmp % base
      overflow = tmp / base

def convertNumber(srcDigits, srcBase, destDigits, destBase):
   for srcDigit in srcDigits:
      multNumberByValue(destDigits, destBase, srcBase)
      incNumberByValue(destDigits, destBase, srcDigit)

def withoutLeadingZeros(digits):
   for i in xrange(len(digits)):
      if digits[i] != 0:
         break
   return digits[i:]

def convertNumberExt(srcDigits, srcBase, destBase):
   # Generate a list of zero's which is long enough to hold the destination number.
   destDigits = [0] * int(math.ceil(len(srcDigits)*math.log(srcBase)/math.log(destBase)))
   # Do conversion.
   convertNumber(srcDigits, srcBase, destDigits, destBase)
   # Return result (without leading zeros).
   return withoutLeadingZeros(destDigits)


# Example: Convert base 10 to base 16
base10 = [int(c) for c in '1234567890987654321234567890987654321234567890987654321']
base16 = convertNumberExt(base10, 10, 16)
# Output list of base 16 digits as HEX string.
hexDigits = '0123456789ABCDEF'
string.join((hexDigits[n] for n in base16), '')
于 2011-05-01T22:52:33.657 に答える
2

本当に難しい部分は、「任意の大きい」符号なし整数です。

GNU MP Bignumライブラリを使用してみましたか？

于 2009-05-13T10:03:33.517 に答える
1

BigIntライブラリは次のとおりです。

http://www.codeproject.com/KB/cs/BigInt.aspx?msg=3038072#xx3038072xx

それが機能するかどうかはわかりませんが、Googleで最初に見つけたものです。大きな整数を解析およびフォーマットする機能があるように見えるので、それらは異なるベースもサポートする可能性があります。

編集：ああ、あなたはCを使用しています、私の間違い。ただし、コードからアイデアを取得できる場合や、.NETを使用している人が同じ質問をする場合があるため、ここに残しておきます。

于 2009-05-13T10:02:05.547 に答える
1

Unixdcは、任意の大きな整数に基づいて基数変換を行うことができます。オープンBSDソースコードはここから入手できます。

于 2009-05-13T10:04:40.190 に答える
0

Python：

>>> from string import upper
>>> input = "1234567890987654321234567890987654321234567890987654321"
>>> output = upper(hex(int(input)))[2:-1]
>>> print output
CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1
于 2009-06-30T15:51:55.203 に答える