不使用乘法 C# 将字符串转换为整数

Question

有没有一种不用乘法就可以将字符串转换为整数的方法。 int.Parse() 的实现也使用了乘法。我还有其他类似的问题，您可以在其中手动将字符串转换为 int，但这也需要将数字乘以 10。这是我在一次面试中遇到的面试问题，我似乎找不到任何关于此的答案。

Answer 1

如果你假设一个基数为 10 的数字系统并用移位 (see here) 代替乘法，这可以是 正整数.[=18 的解决方案=]

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

将数字字符转换为其整数值

编辑：

对于负整数这个版本（see here）有效。

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

视情况而定。我们是在谈论乘法的逻辑运算，还是它在硬件中的实际执行方式？

例如，您可以将十六进制（或八进制，或任何其他以二为底的乘数）字符串转换为整数 "without multiplication"。您可以一个字符一个字符地进行，并保持 oring (|) 和 bitshifting (<<)。这避免了使用 * 运算符。

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

当然，这两者都是变相的乘法。那是因为位置数字系统 本质上是乘法的 。这就是特定数字表示的工作原理。您可以进行简化以隐藏这一事实（例如，二进制数只需要 0 和 1，因此您可以有一个简单的条件而不是相乘 - 当然，你真正做的仍然是乘法，只是只有两个可能的输入和两个可能的输出），但它总是在那里，潜伏着。 <<和* 2是一样的，即使做运算的硬件可以更简单and/or更快

要完全取消乘法，您需要避免使用位置系统。例如，罗马数字是加法的（请注意，实际的罗马数字并没有使用我们今天的紧凑化规则——四将是 IIII，而不是 IV，十四可以写成任何形式XIIII、IIIIX、IIXII、VVIIII 等）。将这样的字符串转换为整数变得非常容易——只需一个字符一个字符地转换，然后继续添加。如果字符是X，则加十。如果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.
}

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

Answer 4

任何乘法都可以用重复的加法代替。因此，您可以将现有算法中的任何乘法替换为仅使用加法的版本：

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

你可以更进一步，使用这个想法将一个专门的 String 写成 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;
}

但我认为这不值得，因为这里的性能似乎不是问题。

不使用乘法 C# 将字符串转换为整数

Converting String to Integer without using Multiplication C#

c#

string

int