извлечение первых 32 битов целого числа ASCII - PullRequest
Новая
       13

извлечение первых 32 битов целого числа ASCII

3 голосов
/ 16 июля 2011

У вас есть строка ASCII, представляющая 128-разрядное целое число без знака n, то есть 0 <= n <2 ^ 128. </p>

Дайте алгоритм для извлечения наиболее значимых 32 бит двоичного представления nи вернуть их в виде 32-разрядного целого числа без знака, которое они кодируют.

Какой быстрый способ сделать это, то есть что-то лучше, чем реализация собственных операций деления большого числа и операций по модулю 2.Предположим, что 32-битный компьютер, т. Е. У вас нет 64-битных встроенных типов.

Примеры. Для краткости возьмем 4-битные целые числа и извлечем первые 2 бита:

2 (0010) -> 0 (00) 7 (0111) -> 1 (01) 8 (1000) -> 2 (10) 13 (1101) -> 3 (11)

ЭтоНЕ домашний вопрос.Обновление моих алго-навыков для интервью.

1 Ответ

1 голос
/ 17 июля 2011

Я не вижу более эффективного способа, чем просто эмулировать (ограниченную форму) 128-битную арифметику.

Допустим, у нас есть функция mul10add(a, b), которая вычисляет 10*a + b и возвращает младшие 32 бита ответа вместе со значением переноса. Если у нас есть 64-битная арифметика, она может быть реализована как (в псевдокоде): 

(word32, word32) mul10add(word32 a, word32 b):
    word64 result = 10*a + b
    word32 carry  = result >> 32
    return (result, carry)

Теперь мы возьмем обычный десятичный-двоичный алгоритм и представим 128-битное число n с четырьмя 32-битными словами x, y, z и w таким, что n = x*2^96 + y*2^64 + z*2^32 + w. Затем мы можем объединить вызовы mul10add вместе, чтобы выполнить эквивалент n = 10*n + digitToInt(decimal[i]). 

word32 high32bits(string decimal):
    word32 x = 0, y = 0, z = 0, w = 0

    # carry
    word32 c = 0

    for i in 0..length(decimal)-1
       (w, c) = mul10add(w, digitToInt(decimal[i]))
       (z, c) = mul10add(z, c)
       (y, c) = mul10add(y, c)
       (x, _) = mul10add(x, c)

    return x

Однако для реализации mul10add нам фактически не нужна 64-битная архитектура. На x86 у нас есть инструкция mul, которая умножает два 32-битных числа, чтобы получить 64-битное число с верхними 32 битами, сохраненными в edx, и младшими в eax. Также есть инструкция adc, которая добавляет два числа, но включает перенос из предыдущего add. Итак, в псевдосборке: 

(word32, word32) mul10add(word32 a, word32 b):
    word32 result, carry
    asm:
        mov a, %eax
        mul 10
        add b, %eax
        adc 0, %edx
        mov %eax, result
        mov %edx, carry
    return (result, carry)
...