Преобразование строки в целое число без использования умножения C#

Question

Есть ли способ преобразовать строку в целое число без использования умножения. Реализация int.Parse () также использует умножение. У меня есть другие подобные вопросы, где вы можете вручную преобразовать строку в int, но это также требует умножения числа на его основание 10. Это был вопрос интервью, который у меня был в одном из интервью, и я не могу найти какой-либо ответ по этому поводу.

Answer 1

Если принять систему счисления с основанием 10 и заменить умножение на сдвиги битов ( см. Здесь ), это может быть решением для натуральных чисел .

public int StringToInteger(string value)
{
    int number = 0;
    foreach (var character in value)
        number = (number << 1) + (number << 3) + (character - '0');

    return number;
}

См. Пример на ideone .

. Предполагается, что символы '0' до '9' l ie находятся непосредственно рядом друг с другом в наборе символов. Символы di git преобразуются в целочисленные значения с использованием character - '0'.

Редактировать:

Для отрицательных целых чисел этой версии ( см. Здесь ) работает.

public static int StringToInteger(string value)
{
    bool negative = false;
    int i = 0;

    if (value[0] == '-')
    {
        negative = true;
        ++i;
    }

    int number = 0;
    for (; i < value.Length; ++i)
    {
        var character = value[i];
        number = (number << 1) + (number << 3) + (character - '0');
    }

    if (negative)
        number = -number;
    return number;
}

В общем случае следует учитывать ошибки, такие как проверки на ноль, проблемы с другими нечисловыми c символами и т. Д. c.

Answer 2

Это зависит. Мы говорим о логической операции умножения или о том, как на самом деле это делается в аппаратном обеспечении?

Например, вы можете преобразовать шестнадцатеричную (или восьмеричную, или любой другой множитель с двумя основными) в целое число "без умножения ». Вы можете go символ за символом и продолжать ориентироваться (|) и сдвигать биты (<<). Это позволяет избежать использования оператора *.

Делать то же самое с десятичными строками сложнее, но у нас все еще есть простое добавление. Вы можете использовать циклы с дополнением, чтобы сделать то же самое. Довольно просто сделать. Или вы можете создать свою собственную «таблицу умножения» - надеюсь, вы научились умножать числа в школе; Вы можете сделать то же самое с компьютером. И, конечно же, если вы работаете на десятичном компьютере (а не на двоичном), вы можете выполнить «битовое смещение», как и в предыдущей шестнадцатеричной строке. Даже с двоичным компьютером вы можете использовать серию битовых сдвигов - (a << 1) + (a << 3) - это то же самое, что и a * 2 + a * 8 == a * 10. Осторожнее с отрицательными числами. Вы можете придумать множество хитростей, чтобы сделать это интересным.

Конечно, оба они являются просто скрытым умножением. Это потому, что позиционные системы c * по своей сути мультипликативны . Вот как работает это конкретное представление цифр c. У вас могут быть упрощения, которые скрывают этот факт (например, двоичные числа нуждаются только в 0 и 1, поэтому вместо умножения вы можете иметь простое условие - конечно, то, что вы на самом деле делаете, это все еще умножение, только с два возможных входа и два возможных выхода), но он всегда есть, скрывается. << совпадает с * 2, даже если аппаратное обеспечение, которое выполняет операцию, может быть проще и / или быстрее.

Чтобы полностью отказаться от умножения, вам следует избегать использования позиционной системы. Например, римские цифры являются аддитивными (обратите внимание, что настоящие римские цифры не использовали правила компактификации, которые мы имеем сегодня - четыре будут IIII, а не IV, и четырнадцать могут быть записаны в любой форме, например XIIII, IIIIX, IIXII, VVIIII et c.). Преобразование такой строки в целое число становится очень простым - просто go символ за символом, и продолжайте добавлять. Если символ X, добавьте десять. Если V, добавьте пять. Если I, добавьте один. Я надеюсь, вы понимаете, почему римские цифры так долго оставались популярными; Позиционные системы c замечательны, когда вам нужно много умножения и деления. Если вы в основном имеете дело с сложением и вычитанием, римские цифры работают отлично и требуют гораздо меньшего количества обучения (а счеты гораздо проще в создании и использовании, чем позиционный калькулятор!).

С такими заданиями, как это то, что на самом деле ожидает интервьюер. Может быть, они просто хотят увидеть ваши мыслительные процессы. Вы принимаете технические детали (<< не является действительно умножением)? Знаете ли вы теорию чисел и информатику? Вы просто погружаетесь в свой код или просите разъяснений? Считаете ли вы это забавным испытанием или еще одним смешным скучным вопросом для собеседования, который не имеет никакого отношения к вашей работе? Мы не можем сказать вам ответ, который искал интервьюер.

Но я надеюсь, что, по крайней мере, вы мельком увидели возможных ответов :)

Answer 3

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

private int StringToInt(string value)
{
    for (int i = int.MinValue; i <= int.MaxValue; i++)
        if (i.ToString() == value)
            return i;
    return 0; // All code paths must return a value.
}

Если переданная строка не является целым числом, метод выдаст исключение переполнения.

Answer 4

Любое умножение можно заменить повторным сложением. Таким образом, вы можете заменить любое умножение в существующем алгоритме версией, которая использует только сложение:

static int Multiply(int a, int b)
{
    bool isNegative = a > 0 ^ b > 0;
    int aPositive = Math.Abs(a);
    int bPositive = Math.Abs(b);
    int result = 0;
    for(int i = 0; i < aPositive; ++i)
    {
        result += bPositive;
    }
    if (isNegative) {
        result = -result;
    }
    return result;
}

Вы можете go продолжить и написать специальную String для Int, используя эту идею, которая минимизирует количество сложений ( отрицательное число и обработка ошибок для краткости опущены):

static int StringToInt(string v)
{
    const int BASE = 10;
    int result = 0;
    int currentBase = 1;
    for (int digitIndex = v.Length - 1; digitIndex >= 0; --digitIndex)
    {
        int digitValue = (int)Char.GetNumericValue(v[digitIndex]);
        int accum = 0;
        for (int i = 0; i < BASE; ++i)
        {
            if (i == digitValue)
            {
                result += accum;
            }
            accum += currentBase;
        }
        currentBase = accum;
    }
    return result;
}

Но я не думаю, что это стоит того, так как производительность здесь не имеет значения.