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

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

Если принять систему счисления с основанием 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'лежать непосредственно рядом друг с другом в наборе символов. Цифровые символы преобразуются в их целочисленные значения с помощью 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;
}

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

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

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

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

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

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

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

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

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

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.
}

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

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

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;
}

Вы можете пойти дальше и написать специальную строку для 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;
}

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