不使用乘法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;
}

参见意为上的示例。

唯一的假设是字符'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;
}

通常，您应该考虑到错误，例如空检查、其他非数字字符的问题等等。

Answer 2

那得看情况。我们是在谈论乘法的逻辑运算，还是它在硬件上的实际操作？

例如，您可以将十六进制(或八进制，或任何其他两个基数的乘法器)字符串转换为“不加乘法”的整数。您可以逐个字符进行跟踪(|)和位移位(<<)。这避免了使用*运算符。

对十进制字符串做同样的操作比较困难，但是我们仍然有简单的加法。您可以使用循环加上加法来做同样的事情。做起来很简单。或者你也可以制作自己的“乘法表”--希望你在学校学会了如何乘数字；你也可以用电脑做同样的事情。当然，如果您在十进制计算机上(而不是二进制)，您可以执行“位移位”，就像前面的十六进制字符串一样。即使使用二进制计算机，也可以使用一系列的位移位-- (a << 1) + (a << 3)与a * 2 + a * 8 == a * 10相同。小心负数。你可以想出很多窍门让这件事变得有趣。

当然，这两个都只是伪装的乘法。这是因为位置数字系统本质上是乘法的。这就是这个特殊的数字表示的工作原理。你可以通过简化来隐藏这个事实(例如二进制数字只需要0和1，所以你可以有一个简单的条件--当然，你真正要做的还是乘法，只有两个可能的输入和两个可能的输出)，但它总是存在的。<<和* 2是一样的，即使执行操作的硬件可以更简单和/或更快。

要完全消除乘法，你需要避免使用位置系统。例如，罗马数字是加性的(请注意，实际的罗马数字没有使用我们现在的紧致规则-四个是IIII，而不是IV，它十四可以用XIIII、IIIIX、IIXII、VVIIII等任何形式编写)。将这样的字符串转换为整数变得非常容易--只需逐个字符，然后继续添加。如果字符为X，则添加10。如果是V，加5。如果是I，添加一个。我希望你能明白为什么罗马数字会持续这么久；当你需要做大量的乘法和除法时，位置数字系统是很棒的。如果您主要处理的是加法和减法，那么罗马数字工作得很好，所需的教育也要少得多(而算盘比位置计算器容易得多！)

有了这样的任务，面试官的实际期望就会有很多的冲击和错过。也许他们只是想看看你的思维过程。你接受技术细节(<<并不是真正的乘法)吗？你懂数论和计算机科学吗？你是直接继续你的代码，还是要求澄清？你认为这是一个有趣的挑战，还是另一个与你的工作无关的荒谬无聊的面试问题？我们不可能告诉你面试官想要的答案。

但我希望我至少能给你一个可能的答案:)

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

如果传递的字符串不是整数，则该方法将引发溢出异常。