Konwertowanie ciągu na liczbę całkowitą bez użycia mnożenia C #

Czy istnieje sposób na konwersję ciągu na liczby całkowite bez użycia mnożenia. Implementacja int.Parse () również wykorzystuje mnożenie. Mam inne podobne pytania, w których można ręcznie przekonwertować ciąg na int, ale to także wymaga wielokrotnego pomnożenia liczby przez jej bazę 10. To było pytanie do wywiadu, które miałem w jednym z wywiadów i wydaje się, że nie mogę znaleźć na to odpowiedzi.

Jeśli przyjmiesz system liczbowy liczby podstawowej 10 i podstawisz mnożenie przez przesunięcia bitów ( patrz tutaj ), może to być rozwiązanie dla dodatnich liczb całkowitych .

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

    return number;
}

Zobacz przykład na ideone .

Jedynym założeniem jest to, że postacie '0'do '9'leżą bezpośrednio obok siebie w zestawie znaków. Znaki cyfr są konwertowane na ich wartości całkowite za pomocą character - '0'.

Edytować:

W przypadku liczb całkowitych ujemnych ta wersja ( patrz tutaj ) działa.

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

Zasadniczo należy wziąć pod uwagę błędy, takie jak kontrole zerowe, problemy z innymi znakami nienumerycznymi itp.

To zależy. Czy mówimy o logicznej operacji mnożenia, czy o tym, jak to się faktycznie robi w sprzęcie?

Na przykład możesz przekonwertować ciąg szesnastkowy (lub ósemkowy lub dowolny inny mnożnik bazowy dwa) na liczbę całkowitą „bez mnożenia”. Możesz iść znak po znaku i zachować oring ( |) i bitshifting ( <<). Pozwala to uniknąć korzystania z *operatora.

Robienie tego samego z łańcuchami dziesiętnymi jest trudniejsze, ale nadal mamy prosty dodatek. Możesz użyć pętli z dodatkiem, aby zrobić to samo. Całkiem proste do zrobienia. Możesz też stworzyć własną „tabliczkę mnożenia” - mam nadzieję, że nauczyłeś się, jak pomnożyć liczby w szkole; możesz zrobić to samo z komputerem. I oczywiście, jeśli korzystasz z komputera dziesiętnego (zamiast binarnego), możesz wykonać „przesunięcie bitów”, podobnie jak w przypadku wcześniejszego ciągu szesnastkowego. Nawet w przypadku komputera binarnego można użyć szeregu przesunięć bitowych - (a << 1) + (a << 3)jest taki sam jak a * 2 + a * 8 == a * 10. Uważaj na liczby ujemne. Możesz wymyślić wiele sztuczek, aby uczynić to interesującym.

Oczywiście oba te elementy są tylko maskowaniem. Jest tak, ponieważ pozycyjne systemy numeryczne są z natury multiplikatywne . Tak działa ta konkretna reprezentacja numeryczna. Można mieć uproszczeń, które ukrywają ten fakt (tylko np liczb binarnych trzeba 0i 1tak zamiast mnożenia, można mieć prosty warunek - oczywiście, co tak naprawdę robi to nadal mnożenie, tylko przy użyciu tylko dwóch możliwych wejść i dwóch możliwych wyjść), ale zawsze tam jest, czai się. <<jest taki sam jak * 2, nawet jeśli sprzęt, który wykonuje operację, może być prostszy i / lub szybszy.

Aby całkowicie zrezygnować z mnożenia, należy unikać używania systemu pozycjonowania. Na przykład, cyfry rzymskie są addytywne (uwaga, że rzeczywiste cyframi rzymskimi nie używać zasad zwartym mamy dzisiaj - cztery byłoby IIIInie IV, i to czternaście może być napisany w jakiejkolwiek formie jak XIIII, IIIIX, IIXII, VVIIIIitd.). Konwersja takiego ciągu na liczbę całkowitą staje się bardzo łatwa - po prostu idź znak po znaku i dodawaj dalej. Jeśli postać jest X, dodaj dziesięć. Jeśli Vdodaj pięć. GdybyI, Dodaj jeden. Mam nadzieję, że zrozumiecie, dlaczego cyfry rzymskie były tak popularne; Pozycyjne systemy numeryczne są cudowne, gdy trzeba dużo powielać i dzielić. Jeśli zajmujesz się głównie dodawaniem i odejmowaniem, cyfry rzymskie działają świetnie i wymagają znacznie mniej nauki (a liczydło jest o wiele łatwiejsze do wykonania i użycia niż kalkulator pozycyjny!).

Przy takich zadaniach istnieje wiele trafień i oczekiwań dotyczących tego, czego faktycznie oczekuje ankieter. Może po prostu chcą zobaczyć twoje procesy myślowe. Czy akceptujesz specyfikacje techniczne ( <<tak naprawdę to nie mnożenie)? Czy znasz teorię liczb i informatykę? Czy po prostu zagłębiasz się w kod, czy prosisz o wyjaśnienia? Czy traktujesz to jako zabawne wyzwanie, czy może kolejne śmieszne, nudne pytanie, które nie ma związku z twoją pracą? Nie możemy powiedzieć ci odpowiedzi, której szukał ankieter.

Ale mam nadzieję, że przynajmniej rzuciłem okiem na możliwe odpowiedzi :)

Biorąc pod uwagę, że jest to pytanie do wywiadu, wydajność może nie mieć wysokiego priorytetu. Dlaczego nie tylko:

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

Jeśli przekazany ciąg nie jest liczbą całkowitą, metoda zgłosi wyjątek przepełnienia.

Każde zwielokrotnienie można zastąpić przez wielokrotne dodawanie. Możesz więc zastąpić dowolną wielokrotność w istniejącym algorytmie wersją, która używa tylko dodawania:

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

Możesz pójść dalej i napisać specjalistyczny ciąg znaków do Int, korzystając z tego pomysłu, który minimalizuje liczbę dodatków (pominięto liczbę ujemną i obsługę błędów):

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

Ale nie sądzę, żeby było to warte kłopotu, ponieważ wydajność nie wydaje się tutaj stanowić problemu.