Convertendo String em Inteiro sem usar Multiplicação C #

Existe uma maneira de converter string em números inteiros sem usar a Multiplicação. A implementação de int.Parse () também usa multiplicação. Tenho outras perguntas semelhantes, nas quais você pode converter manualmente a string para int, mas isso também exige que o número seja multiplicado por sua base 10. Essa foi uma pergunta de entrevista que tive em uma das entrevistas e não consigo encontrar nenhuma resposta sobre isso.

Se você assumir um sistema de números da base 10 e substituir a multiplicação por turnos de bits ( veja aqui ), isso pode ser uma solução para números inteiros positivos .

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

    return number;
}

Veja o exemplo em ideone .

A única assunção é que os caracteres '0'para '9'deitar directamente ao lado do outro no conjunto de caracteres. Os dígitos dos caracteres são convertidos em seu valor inteiro usando character - '0'.

Editar:

Para números inteiros negativos, esta versão ( veja aqui ) funciona.

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

Em geral, você deve considerar erros como verificações nulas, problemas com outros caracteres não numéricos etc.

Depende. Estamos falando da operação lógica da multiplicação ou de como ela é realmente feita no hardware?

Por exemplo, você pode converter uma sequência hexadecimal (ou octal ou qualquer outro multiplicador de base dois) em um número inteiro "sem multiplicação". Você pode caracterizar caractere e manter oring ( |) e bitshifting ( <<). Isso evita o uso do *operador.

Fazer o mesmo com seqüências decimais é mais complicado, mas ainda temos uma adição simples. Você pode usar loops com adição para fazer a mesma coisa. Muito simples de fazer. Ou você pode criar sua própria "tabuada de multiplicação" - espero que tenha aprendido a multiplicar números na escola; você pode fazer a mesma coisa com um computador. E, é claro, se você estiver em um computador decimal (em vez de binário), poderá executar o "deslocamento de bits", como na string hexadecimal anterior. Mesmo com um computador binário, você pode usar uma série de turnos de bits - (a << 1) + (a << 3)é o mesmo que a * 2 + a * 8 == a * 10. Cuidado com números negativos. Você pode descobrir muitos truques para tornar isso interessante.

Obviamente, ambos são apenas multiplicação disfarçada. Isso ocorre porque os sistemas numéricos posicionais são inerentemente multiplicativos . É assim que essa representação numérica específica funciona. Você pode ter simplificações que ocultam esse fato (por exemplo, os números binários precisam apenas 0e 1, em vez de se multiplicar, você pode ter uma condição simples - é claro, o que você realmente está fazendo ainda é a multiplicação, apenas com apenas duas entradas possíveis e duas possíveis. saídas), mas está sempre lá, à espreita. <<é o mesmo que * 2, mesmo que o hardware que executa a operação possa ser mais simples e / ou mais rápido.

Para eliminar completamente a multiplicação, você precisa evitar o uso de um sistema posicional. Por exemplo, numerais romanos são aditivos (note que algarismos romanos reais não usar as regras compactification que temos hoje - quatro seria IIII, não IV, e quatorze poderia ser escrito em qualquer forma, como XIIII, IIIIX, IIXII, VVIIIIetc.). A conversão dessa string em número inteiro torna-se muito fácil - basta caractere por caractere e continue adicionando. Se o personagem for X, adicione dez. Se Vadicionar cinco. E seI, Adicione um. Espero que você possa ver por que os algarismos romanos permaneceram populares por tanto tempo; sistemas numéricos posicionais são maravilhosos quando você precisa fazer muita multiplicação e divisão. Se você lida principalmente com adição e subtração, os algarismos romanos funcionam muito bem e exigem muito menos escolaridade (e um ábaco é muito mais fácil de criar e usar do que uma calculadora posicional!).

Em tarefas como essa, há muita coisa sobre o que o entrevistador realmente espera. Talvez eles só querem ver seus processos de pensamento. Você adota tecnicismos ( <<não é realmente multiplicação)? Você conhece teoria dos números e ciência da computação? Você apenas mergulha no seu código ou pede esclarecimentos? Você vê isso como um desafio divertido ou como mais uma pergunta de entrevista ridícula e chata que não tem nenhuma relevância para qual é o seu trabalho? É impossível dizer a resposta que o entrevistador estava procurando.

Mas espero ter, pelo menos, um vislumbre de possíveis respostas :)

Considerando que é uma pergunta de entrevista, o desempenho pode não ser uma alta prioridade. Por que não apenas:

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

Se a sequência passada não for um número inteiro, o método lançará uma exceção de estouro.

Qualquer multiplicação pode ser substituída por adição repetida. Portanto, você pode substituir qualquer multiplicação em um algoritmo existente por uma versão que use apenas a adição:

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

Você poderia ir além e escrever uma String especializada em Int usando essa ideia que minimiza o número de adições (número negativo e manipulação de erros omitidos por questões de brevidade):

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

Mas acho que não vale a pena, pois o desempenho não parece ser uma preocupação aqui.