Java 中的 Luhn 校验和验证

Question

我必须在 Java 中复制 luhn 算法，我面临的问题是如何以高效和优雅的方式实现它（不是必需的，但这是我想要的）。

luhn 算法的工作原理如下：

你取一个数字，比如说56789

循环下一步，直到没有数字剩余

您选择最左边的数字并将其添加到总和中。 sum = 5
你舍弃这个数字然后去下一个。 number = 6789
你把这个数字加倍，如果它超过一位数，你把这个数字分开，然后把它们分别加到总和上。 2*6 = 12，所以 sum = 5 + 1 = 6 然后 sum = 6 + 2 = 8。

添加限制 对于这个特殊问题，我需要一次读取所有数字并在继续之前分别对每个数字进行计算。我还假设所有数字都是正数。

我面临的问题和存在的疑问

如前所述，我尝试以一种优雅高效的方式解决这个问题。这就是为什么我不想在数字上调用 toString() 方法来访问需要大量转换的所有单个数字。我也不能使用模数的方式，因为上面的限制表明，一旦我读取了一个数字，我也应该立即对其进行计算。如果我事先知道字符串的长度，我只能使用模数，但这感觉就像我首先必须一次计算所有数字，因此违反了限制。现在我只能想到一种方法来做到这一点，但这也需要大量的计算并且只关心第一个数字*：

int firstDigit(int x) {
    while (x > 9) {
        x /= 10;
    }
    return x;
}

在此处找到：

*然而，当我想到它时，这基本上是一种不同且奇怪的方式来利用数字的长度属性，通过将它经常除以直到剩下一个数字。

所以基本上我现在被卡住了，我想我必须使用它实际上没有的数字的长度属性，所以我应该手动找到它。有没有好的方法来做到这一点？现在我在想我应该结合使用模数和数字的长度。这样我就知道总位数是奇数还是偶数，然后我可以从右到左进行计算。只是为了好玩，我认为我可以使用它来提高效率来获取数字的长度：

这个问题出现在 Think like a programmer 这本书中。

Answer 1

您可以通过展开循环一次（或任意多次）来优化它。对于大数，这将快两倍，但是让小数变慢。如果您知道您将拥有的典型数字范围，您可以确定展开此循环的数量。

int firstDigit(int x) {
    while (x > 99)
        x /= 100;
    if (x > 9) 
        x /= 10;
    return x;
}

Answer 2

据我了解，您最终需要读取每个数字，因此将初始数字转换为字符串（因此 char[]）有什么问题，然后您可以轻松地实现迭代该 char 数组的算法。

JDK Integer.toString 的实现是相当优化的，因此您需要实现自己的优化，例如它使用不同的查找表来优化转换，一次转换两个字符等。

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };

// Requires positive x
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}

这只是一个示例，但请随时检查完整的实现:)

Answer 3

通常情况下，您会使用除以 10 的方式从右向左处理数字以移动数字并以 10 为模以提取最后一位。从左到右处理数字时，您仍然可以使用此技术。只需使用除以 1000000000 来提取第一个数字并乘以 10 将其左移：

其中一些数字超过了 int 的最大值。如果你必须支持全范围的输入，你将不得不存储长的数字：

static int checksum(int x) {
    long n = x;
    int sum = 0;
    while (n != 0) {
        long d = 1000000000l;
        int digit = (int) (n / d);
        n %= d;
        n *= 10l;
        // add digit to sum
    }
    return sum;
}

Answer 4

我会先将数字转换成一种 BCD（二进制编码的十进制）。我不确定能否找到比 JDK Integer.toString() 转换方法更好的优化方法，但正如您所说，您不想使用它：

List<Byte> bcd(int i) {
    List<Byte> l = new ArrayList<Byte>(10);  // max size for an integer to avoid reallocations
    if (i == 0) {
        l.add((byte) i);
    }
    else {
        while (i != 0) {
            l.add((byte) (i % 10));
            i = i / 10;
        }
    }
    return l;
}

这或多或少是您提出的获取第一个数字的方法，但现在您一次通过就拥有了所有数字，并且可以将它们用于您的算法。

我建议使用byte，因为它足够了，但是java总是转换成int来计算，直接使用List<Integer>可能会更高效，即使它真的很浪费内存.

Answer 5

使用org.apache.commons.validator.routines.checkdigit.LuhnCheckDigit。是有效的（）

Maven 依赖：

<dependency>
    <groupId>commons-validator</groupId>
    <artifactId>commons-validator</artifactId>
    <version>1.4.0</version>
</dependency>

Java 中的 Luhn 校验和验证

Luhn checksum validation in Java

java

algorithm

luhn 算法的工作原理如下：

我面临的问题和存在的疑问