Mengubah String ke Integer tanpa menggunakan Perkalian C #

Apakah ada cara untuk mengkonversi string ke integer tanpa menggunakan Perkalian. Implementasi int.Parse () juga menggunakan multiplikasi. Saya punya pertanyaan serupa lainnya di mana Anda dapat secara manual mengkonversi string ke int, tetapi itu juga memerlukan mulitiplying nomor dengan basisnya 10. Ini adalah pertanyaan wawancara yang saya miliki dalam salah satu wawancara dan sepertinya saya tidak dapat menemukan jawaban mengenai hal ini.

Jika Anda mengasumsikan sistem bilangan dasar-10 dan mengganti perkaliannya dengan pergeseran bit ( lihat di sini ) ini bisa menjadi solusi untuk bilangan bulat positif .

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

    return number;
}

Lihat contoh di ideone .

Satu-satunya asumsi adalah bahwa karakter '0'untuk '9'berbohong langsung di sebelah satu sama lain dalam set karakter. Digit-karakter dikonversi ke nilai integernya menggunakan character - '0'.

Edit:

Untuk bilangan bulat negatif , versi ini ( lihat di sini ) berfungsi.

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

Secara umum Anda harus memperhitungkan kesalahan seperti cek nol, masalah dengan karakter non-numerik lainnya, dll.

Tergantung. Apakah kita berbicara tentang operasi logis dari perkalian, atau bagaimana itu sebenarnya dilakukan dalam perangkat keras?

Misalnya, Anda dapat mengubah string heksadesimal (atau oktal, atau basis dua pengganda lainnya) menjadi bilangan bulat "tanpa perkalian". Anda dapat menggunakan karakter demi karakter dan tetap menggunakan oring ( |) dan bitshifting ( <<). Ini menghindari penggunaan *operator.

Melakukan hal yang sama dengan string desimal lebih sulit, tetapi kami masih memiliki penambahan sederhana. Anda dapat menggunakan loop dengan tambahan untuk melakukan hal yang sama. Cukup sederhana untuk dilakukan. Atau Anda bisa membuat "tabel perkalian" sendiri - semoga Anda belajar cara melipatgandakan angka di sekolah; Anda dapat melakukan hal yang sama dengan komputer. Dan tentu saja, jika Anda menggunakan komputer desimal (bukan biner), Anda dapat melakukan "bitshift", seperti halnya dengan string heksadesimal sebelumnya. Bahkan dengan komputer biner, Anda dapat menggunakan serangkaian bitshift - (a << 1) + (a << 3)sama seperti a * 2 + a * 8 == a * 10. Hati-hati dengan angka negatif. Anda dapat menemukan banyak trik untuk membuat ini menarik.

Tentu saja, keduanya hanyalah perkalian yang tersamar. Itu karena sistem numerik posisional bersifat multiplikasi . Begitulah cara kerja representasi numerik tertentu. Anda dapat memiliki penyederhanaan yang menyembunyikan fakta ini (mis. Angka biner hanya perlu 0dan 1, jadi alih-alih mengalikannya, Anda dapat memiliki kondisi yang sederhana - tentu saja, apa yang sebenarnya Anda lakukan adalah perkalian, hanya dengan hanya dua input yang mungkin dan dua kemungkinan) output), tapi selalu ada di sana, mengintai. <<sama dengan * 2, bahkan jika perangkat keras yang melakukan operasi dapat lebih sederhana dan / atau lebih cepat.

Untuk menghilangkan perkalian sepenuhnya, Anda harus menghindari penggunaan sistem posisi. Misalnya, angka romawi adalah aditif (catatan bahwa angka romawi yang sebenarnya tidak menggunakan aturan kompaktifikasi kita miliki saat ini - empat akan IIII, tidak IV, dan itu empat belas dapat ditulis dalam bentuk apapun seperti XIIII, IIIIX, IIXII, VVIIIIdll). Mengubah string menjadi integer menjadi sangat mudah - cukup ikuti karakter demi karakter, dan terus tambahkan. Jika karakternya adalah X, tambahkan sepuluh. Jika V, tambahkan lima. JikaI, tambahkan satu. Saya harap Anda bisa melihat mengapa angka romawi tetap populer untuk waktu yang lama; sistem numerik posisi sangat bagus ketika Anda perlu melakukan banyak perkalian dan pembagian. Jika Anda terutama berurusan dengan penjumlahan dan pengurangan, angka romawi berfungsi dengan baik, dan membutuhkan lebih sedikit pendidikan (dan sempoa jauh lebih mudah dibuat dan digunakan daripada kalkulator posisional!).

Dengan tugas seperti ini, ada banyak untung-untungan tentang apa yang sebenarnya diinginkan pewawancara. Mungkin mereka hanya ingin melihat proses pemikiran Anda. Apakah Anda merangkul masalah teknis ( <<tidak benar - benar multiplikasi)? Apakah Anda tahu teori angka dan ilmu komputer? Apakah Anda hanya terjun dengan kode Anda, atau meminta klarifikasi? Apakah Anda melihatnya sebagai tantangan yang menyenangkan, atau pertanyaan wawancara yang membosankan dan konyol yang tidak memiliki relevansi dengan pekerjaan Anda? Tidak mungkin bagi kami untuk memberi tahu Anda jawaban yang dicari pewawancara.

Tapi saya harap saya setidaknya memberi Anda sekilas kemungkinan jawaban :)

Mengingat itu menjadi pertanyaan wawancara, kinerja mungkin bukan prioritas tinggi. Kenapa tidak adil:

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

Jika string yang diteruskan bukan bilangan bulat, metode ini akan melempar pengecualian overflow.

Perkalian apa pun dapat diganti dengan penambahan berulang. Jadi, Anda dapat mengganti perkalian dalam algoritme yang ada dengan versi yang hanya menggunakan tambahan:

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

Anda bisa melangkah lebih jauh dan menulis String khusus ke Int menggunakan ide ini yang meminimalkan jumlah penambahan (angka negatif dan penanganan kesalahan dihilangkan untuk singkatnya):

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

Tapi saya tidak berpikir itu sepadan dengan masalah karena kinerja tampaknya tidak menjadi masalah di sini.