How to build a string representation of an integer in any base without bitwise operators

doug
Sun, 28 Feb 2010 21:25:03 +0000

Last week I gave the geeks at #neverfear IRC a coding task, something I've been trying lately to both challenge them and myself. The challenge I gave them was actually a real-life problem I'd faced in industry as a developer. The challenge was as follows.

Produce an algorithm in the language of your choice that recursively converts a numerical value to a hexidecimal string without bitwise operators. Bonus points awarded for generalising your algorithm to the nth base.

We had a few good solutions mostly following a similiar approach in various languages that I'd like to share.

Python (Procedural)

def inttobase_worker(x, symset, base):
    if x < base:
        return symset[x]
    else:
        return inttobase( x / base, symset ) + inttobase( x % base, symset )

def inttobase(x, symset):
    return inttobase_worker(x, symset, len(symset))

Invoked as follows:

inttobase(0xDEAD, list("0123456789ABCDEF"))

Python (Lambda)

f = lambda x, sym, base : (
    (x < base)    # if
    and (
        sym[x]    # then
    )
    or (          # else
        f( x / base, sym, base ) + f( x % base, sym, base )
    )
)
g = lambda x, sym : f(x, sym, len(sym))

Invoked as follows:

g(0xDEAD, list("0123456789ABCDEF"))

Note that in this case, none of the symbols can be null or evaluate to false or the conditional construct in the lambda expression falls apart. Fortunately given sanity, rationality and all those good things this should never happen.

Common LISP

By franki^

(defun convert-to-base (number base answer)
  (if (< number base)
      (string-concat (write-to-string number) answer)
      (convert-to-base (floor number base)
                       base
                       (string-concat (write-to-string (rem number base)) answer))))

His approach only works for any base greater than or equal to 2 and less than or equal to 10.

Invoked as follows:

(convert-to-base 222 2 "")

By me

(defun inttobase-worker(v sym base)
    (if (< v base)
        (nth v sym)
        (concatenate
            'string
            (inttobase-worker (floor (/ v base)) sym base)
            (inttobase-worker (mod v base) sym base)
        )
    )
)
(defun inttobase(v sym)
    (let
        (
            (base (list-length sym))
        )
        (inttobase-worker v sym base)
    )
)

Invoked as follows:

(inttobase x (list "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F")

C

By bryno

void to_base(const int num, const int base, char* digits, const size_t pos)
{
    int digit = num % base;
    if (digit > 9)
        digits[pos] = (char)(digit - 10 + 'a');
    else
        digits[pos] = (char)(digit + '0');

    if (pos != 0)
        to_base(num / base, base, digits, pos - 1);
}

char* to_base_r(const int num, const int base)
{
    int num_digits;

    if (num < 0 || base < 2 || base > 26 + 10)
        return NULL;
    else if (num > 0)
        num_digits = (int)(log10(num) / log10(base) + 1);
    else
        num_digits = 1;

    char* digits = new char[num_digits + 1];
    to_base(num, base, digits, num_digits - 1);
    digits[num_digits] = '\0';
    return digits;
}

Invoked as follows

char* digits = to_base_r(num, base);