检查拼写数字是否在c++的范围内

I want to check the (numeric) input against a list of ranges (min,max) while the input is partially typed in; in other words, I need an elegant algorithm to check the prefix of a number against a range (without using regular expressions).

我想检查(数字)输入与范围列表(最小，最大)，而输入是部分输入;换句话说，我需要一个优雅的算法来根据范围检查数字的前缀(不使用正则表达式)。

Sample testcases:

样品测试:

 1 is in (  5,   9) -> false
 6 is in (  5,   9) -> true
 1 is in (  5,  11) -> true  (as 10 and 11 are in the range)
 1 is in (  5, 200) -> true  (as e.g. 12 and 135 are in the range)
11 is in (  5,  12) -> true
13 is in (  5,  12) -> false 
13 is in (  5,  22) -> true
13 is in (  5, 200) -> true  (as 130 is in the range)
 2 is in (100, 300) -> true  (as 200 is in the range)

Do you have any idea?

你知道吗?

15 个解决方案

#1

I believe it's true that the input is acceptable if and only if either:

我相信，输入是可以接受的，如果且仅为:

• It is a prefix substring of the lower bound converted to string
• 它是下界转换为字符串的前缀子字符串。

or

或

• The input followed by any number of additional zeros (possibly none) falls into the range
• 输入后面跟着任何数目的额外的零(可能没有)都属于这个范围

The first rule is required by e.g. 13 is in range (135, 140). The second rule is required by e.g. 2 is in range (1000, 3000).

第一个规则被例13要求在范围内(135,140)。第二个规则被例2所要求，在范围内(1000,3000)。

The second rule can be efficiently tested by a series of multiplies by 10, until the scaled input exceeds the upper bound.

第二个规则可以通过一系列乘以10来有效地测试，直到缩放的输入超过上限。

#2

An iterative formulation:

一个迭代公式:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;    // FIXME handle negative and zero-prefixed numbers
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

A simpler [edit: and more efficent; see below] method is to use truncating integer division:

一个更简单的[编辑:更有效;方法是使用截断整数除法:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

---

Testing and profiling:

测试和分析:

#include <iostream>
#include <chrono>

bool ecatmur_in_range_mul(int input, int min, int max)
{
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

bool ecatmur_in_range_div(int input, int min, int max)
{
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

bool t12_isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};

struct test { int input, min, max; bool result; } tests[] = {
{  1,   5,   9, false },
{  6,   5,   9, true },
{  1,   5,  11, true }, // as 10 and 11 are in the range
{  1,   5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11,   5,  12, true },
{ 13,   5,  12, false },
{ 13,   5,  22, true },
{ 13,   5, 200, true }, // as 130 is in the range
{  2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
    for (auto a: algos)
        for (auto t: tests)
            if (a.fn(t.input, t.min, t.max) != t.result)
                std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
                    << t.result << "\n";

    for (auto a: algos) {
        std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
        for (auto t: tests)
            for (int i = 1; i < t.max * 2; ++i)
                for (volatile int j = 0; j < 1000; ++j) {
                    volatile bool r = a.fn(i, t.min, t.max);
                    (void) r;
                }
        std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
        std::cout << a.name << ": "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
    }
}

Surprisingly (at least to me) iterated division comes out fastest:

令人惊讶的是(至少对我来说)迭代除法出现得最快:

ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000

#3

bool isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

It pass all your testcases.

它通过了所有的测试用例。

#4

One trivial solution is to generate all N-digit prefixes in range. So, for 11 is in ( 5, 12) you want the two-digit prefixes of all numbers between 5 and 12. Obviously that's just 10, 11 and 12.

一个简单的解决方案是在范围内生成所有n位的前缀。11在(5,12)中你想要5到12之间的所有数字的两位数的前缀。显然是10 11 12。

In general, for numbers X to Y, the possible N-digit prefixes can be obtained by the following algorithm:

一般来说，对于数字X到Y，可以通过以下算法得到可能的n位前缀:

X = MIN(X, 10^(N-1) ) ' 9 has no 2-digit prefix so start at 10
Y = Y - (Y MOD 10^N)  ' 1421 has the same 2 digit prefix as 1400
WHILE (X < Y)
  LIST_PREFIX += PREFIX(N, X) ' Add the prefix of X to the list.
  X += 10^(TRUNCATE(LOG10(X)) - N+1) ' For N=2, go from 1200 to 1300

#5

Given a value n, begin with the half-open range [n, n + 1) and proceed by orders of magnitude:

给定一个值n，从半开放范围[n, n + 1]开始，按数量级进行:

• [10n, 10(n + 1))
• (10 n(n + 1))
• [100n, 100(n + 1))
• (100 n,100(n + 1))
• [1000n, 1000(n + 1))
• (1000 n,1000(n + 1))
• …
• …

Continue until the iterated range overlaps the target range, or the two ranges can no longer overlap.

继续，直到迭代范围与目标范围重叠，或者这两个范围不再重叠。

#include <iostream>

bool overlaps(int a, int b, int c, int d) {
  return a < c && c < b || c < a && a < d;
}

bool intersects(int first, int begin, int end) {
  int last = first + 1;
  ++end;
  while (first <= end) {
    if (overlaps(first, last, begin, end))
      return true;
    first *= 10;
    last *= 10;
  }
  return false;
}

int main(int argc, char** argv) {
  std::cout << std::boolalpha
    << intersects( 1,   5,   9) << '\n'
    << intersects( 6,   5,   9) << '\n'
    << intersects( 1,   5,  11) << '\n'
    << intersects( 1,   5, 200) << '\n'
    << intersects(11,   5,  12) << '\n'
    << intersects(13,   5,  12) << '\n'
    << intersects(13,   5,  22) << '\n'
    << intersects(13,   5, 200) << '\n'
    << intersects( 2, 100, 300) << '\n'
    << intersects(13, 135, 140) << '\n';
}

Using ranges is necessary to prevent missed cases. Consider n = 2 and a target range of [21, 199]. 2 is not in the range, so we multiply by 10; 20 is not in the range, so we multiply by 10 again; 200 is not in the range, nor any higher number, so the naive algorithm terminates with a false negative.

使用范围是必要的，以防止遗漏的情况。考虑n = 2，目标范围为[21,199]。2不在范围内，所以乘以10;20不在范围内，我们再乘以10;200不在范围内，也不在任何更高的数字内，所以朴素算法以假阴性结束。

#6

I prefer an approach which uses already implemented algorithms. While a lot of other solution use recursive divisions by 10, I think it's better to make use of 10-base logarithms, which have O(1) complexity, so that the whole solution complexity is O(1).

我更喜欢使用已经实现的算法的方法。虽然很多其他的解决方案都是用10的递归除法，但是我认为最好使用10的对数，它的复杂度是O(1)，所以整个解决方案的复杂度是O(1)。

Let us split the problem into two parts.

让我们把问题分成两部分。

First part will handle the case when the number * 10^n is between min and max for at least one n. This would let us check for example if number = 12 and min,max = 11225,13355, that x = 12000 = 12*10^3 is between min and max. If this test checks out, it means the result is True.

第一部分将处理情况* 10 ^ n是min和max之间至少有一个n。这将让我们检查例如如果数量= 12分钟,max = 11225,13355年,x = 12000 = 12 * 10 ^ 3 min和max之间。如果这个测试检验出来，这意味着结果是正确的。

Second part will handle the cases when number is beginning of either min or max. For example if number = 12 and min,max = 12325,14555, the first test will fail, as 12000 is not between min and max (as well as will fail all other numbers 12*10^n for any n). But second test will find that 12 is the beginning of 12325 and return True.

第二部分将处理数开始为最小或最大值的情况。例如如果数量= 12分钟,max = 12325,14555年,第一个测试将失败,12000不是min和max(以及失败所有其他数字12 * 10 ^ n n)。但第二测试会发现12是12325年初,返回True。

First

Let's check, if the first x = number*10^n, which is equal or larger than min, is smaller or equal than max (so min <= x <= max, where x is number*10^n for any integer n). If it's bigger than max, than all other xes will be bigger, as we took the smallest.

让我们检查,如果第一个x =数量* 10 ^ n,等于或大于最小值,或等于小于最大值(最小值< = x < = max,其中x是数量* 10 ^ n对于任何整数n)。如果是比最大,比其他所有换成大的,当我们把最小的。

log(number*10^n) > log(min)
log(number) + log(10^n) > log(min)
log(number) + n > log(min)
n > log(min) - log(number)
n > log(min/number)

To get the number to compare with, we just calculate the first satisfactory n:

为了得到要比较的数，我们只需要计算第一个满意的n:

n = ceil(log(min/number))

And calculate then number x:

然后计算x:

x = number*10^n

Second

We should check if our number is a literal beginning of either boundary.

我们应该检查我们的数字是否是两个边界的文字开头。

We just calculate x beginning with the same digits as number and padded with 0s on the end, having the same length as min:

我们只是计算x开始时的数字与数字相同，最后是0，长度与min相同:

magnitude = 10**(floor(log10(min)) - floor(log10(number)))
x = num*magnitude

And then check if min's and x difference (in magnitude scale) is less than 1 and bigger or equal to 0:

然后检查min和x的差值(在大小尺度上)小于1，大于等于0:

0 <= (min-x)/magnitude < 1

So, if number is 121 and min is 132125, then magnitude is 1000, x = number*magnitude would be 121000. min - x gives 132125-121000 = 11125, which should be smaller than 1000 (otherwise min beginning would be bigger than 121), so we compare it with magnitude by dividing by it's value and comparing to 1. And it's OK if min is 121000, but not OK if min is 122000, that is why 0 <= and < 1.

如果数字是121，最小值是132125，那么大小是1000,x =数字*大小是121000。min - x得到132125-121000 = 11125，应该小于1000(否则min开始会大于121)，所以我们将它与大小进行比较，除以它的值，然后与1进行比较。如果最小值是121000，也可以，但如果最小值是122000，那就是0 <=和< 1。

The same algorithm is for max.

max也是同样的算法。

Pseudo code

Incorporating it all in pseudo code gives this algorithm:

将其全部合并到伪代码中，就得到了这个算法:

def check(num,min,max):
    # num*10^n is between min and max
    #-------------------------------
    x = num*10**(ceil(log10(min/num)))
    if x>=min and x<=max: 
        return True

    # if num is prefix substring of min
    #-------------------------------
    magnitude = 10**(floor(log10(min)) - floor(log10(num)))
    if 0 <= (min-num*magnitude)/magnitude < 1:
        return True

    # if num is prefix substring of max
    #-------------------------------
    magnitude = 10**(floor(log10(max)) - floor(log10(num)))
    if 0 <= (max-num*magnitude)/magnitude < 1:
        return True

    return False

This code could be optimized by avoiding repeated calculations of log10(num). Also, in final solution I would go from float to integer scope (magnitude = 10**int(floor(log10(max)) - floor(log10(num)))) and then perform all comparisons without division, i.e. 0 <= (max-num*magnitude)/magnitude < 1 -> 0 <= max-num*magnitude < magnitude. This would alleviate possibilities of round-off errors.

可以通过避免重复计算log10(num)来优化此代码。此外，在最终的解决方案中，我将从浮点数到整型范围(大小= 10* int(楼层(log10(max))) -楼层(log10(num (num))))))，然后执行所有的比较，没有分割，即0 <= (max-num*大小)/大小< 1 -> <= max-num*大小 <星等。这将减少舍入误差的可能性。< p>

Also, it may be possible to replace magnitude = 10**(floor(log10(min)) - floor(log10(num))) with magnitude = 10**(floor(log10(min/num))), where log10 is calculated only once. But I can't prove that it will always bring correct results, nor can I disprove it. If anybody could prove it, I would be very grateful.

此外，还可以将震级= 10**(楼层(log10(min))) -楼层(log10(num)))替换为震级= 10**(楼层(楼层(log10(min/num))))，其中log10只计算一次。但是我不能证明它总会带来正确的结果，我也不能证明它。如果有人能证明这一点，我将非常感激。

_{Tests (in Python): http://ideone.com/N5R2j (you could edit input to add another tests).}

测试(在Python中):http://ideone.com/N5R2j(您可以编辑输入以添加另一个测试)。

#7

I came to this new simple solution while thinking on a proof for @Ben Voigt 's beautiful solution:

我想到了这个新的简单的解决方案，同时考虑了一个关于@Ben Voigt的漂亮解决方案的证明:

Let's go back to elementary school where we did number comparison. Question would be like: check if the number "A" is in the range of number "B" and number "C"

让我们回到我们做数字比较的小学。问题是这样的:检查数字“A”是否在数字“B”和数字“C”之间

Solution: Adding the necessary Zeros to the left side of numbers (so we have equal number of digits in all numbers) We start from the leftmost digit. compare it with the equivalent digit in the other two numbers.

解决方案:在数字的左边加上必要的零(所以所有数字的位数都是相等的)我们从最左边的数字开始。将它与其他两个数字中的等效数字进行比较。

• if the digit from A is less than the digit from B or more than the digit from C, then A is not in the range.

  如果A的数字小于B的数字或大于C的数字，则A不在范围内。

• if not we repeat the process with the next digit from A and equivalents from B and C.

  如果不是，我们用A的下一个数字和B和C的等价物重复这个过程。

IMPORTANT QUESTION: Why don't we stop right there? Why do we check the next digits?

重要问题:我们为什么不就此打住呢?为什么要检查下一个数字呢?

IMPORTANT ANSWER: Because the digit from A being between the equivalents from B and C is O.K. up to now but not enough reason yet to make a decision! (obvious right?)

重要的回答:因为A在B和C之间的数字是ok的，但是还没有足够的理由来做决定!(明显的对吗?)

This, in turn, means there could be a set of digits which could put A out of the range.

反过来，这意味着可能有一组数字可以把a排除在范围之外。

AND, LIKEWISE

而且,同样

There could be a set of digits which could put A inside the range

可能有一组数字可以把a放在范围内

which is another way of saying A could be a prefix of a number in the range.

这是另一种说法A可以是范围内数字的前缀。

Isn't that what we were looking for?! :D

这不是我们要找的吗?!:D

The backbone of the algorithm would be basically a simple comparison for each input event:

算法的主干基本上就是对每个输入事件进行简单的比较:

1. Add some zero (if necessary) at the left of min so that the length of min and max would become equal.
2. 在最小值的左边加一些0(如果有必要的话)，使最小值和最大值的长度相等。
3. compare input A with the equivalent digits from min and max (cut the corresponding digits of min and max from left, and not right)
4. 将输入A与min和max的等效数字进行比较(将min和max的对应数字从左裁掉，不要从右裁掉)
5. Is input A <= corresponding part of max AND >= corresponding part of min? (no: return false, yes: return true)
6. 输入A <= max的对应部分，>= min的对应部分?(no: return false, yes: return true)

false and true here express the situation "up to now", as the problem requires.

这里的false和true按照问题的要求表达了“到目前为止”的情况。

#8

(input >= lower_bound) && input <= upper_bound

OR

(f(input) >= lower_bound) && (f(input) <= upper_bound)

OR

(lower_bound - f(input) < pow(10, n_digits_upper_bound - n_digits_input)) && 
(lower_bound - f(input) > 0)

where

f(input) == (input * pow(10, n_digits_upper_bound - n_digits_input))


 1 is in (  5,   9) -> 1 * pow(10,0) -> same                 -> false
 6 is in (  5,   9)                                          -> true
 1 is in (  5,  11) -> 1 * pow(10,1)  -> 10 is in (5,11)     -> true
 1 is in (  5, 200) -> 1 * pow(10,2)  -> 100 is in (5, 200)  -> true
11 is in (  5,  12)                                          -> true
13 is in (  5,  12) -> 13 * pow(10,0) -> same                -> false 
13 is in (  5,  22)                                          -> true
13 is in (  5, 200)                                          -> true
 2 is in (100, 300) -> 2 * pow(10,2) -> 200 is in (100,300)  -> true
 4 is in (100, 300) -> 4 * pow(10,2)  -> 400 is in (100,300) -> false
13 is in (135, 140) -> 135 - 130                             -> true
14 is in (135, 139) -> 135 - 140                             -> false

#9

All the hard cases are situations in which the lower bound has less digits then the upper bound. Just break the range in two (or three). If AB is the union of sets A and B, then x in AB implies x in A or x in B. So:

所有的硬情况都是下界的数字比上界少。只要把范围分成两(或三)个就可以了。如果AB是集合A和B的并集，那么AB中的x意味着A中的x或者B中的x，所以:

13 is in (5, 12) => 13 is in (5, 9) OR 13 is in (10, 12)

13在(5,12)=> 13在(5,9)或13在(10,12)

13 is in (5, 120) => 13 is in (5, 9) OR 13 is in (10, 99) OR 13 is in (100, 120)

13在(5,120)=> 13在(5,9)或13在(10,99)或13在(100,120)

Then, truncate to match lengths. I.e.

然后，截断以匹配长度。即。

13 is in (5, 120) => 13 is in (5, 9) OR 13 is in (10, 99) OR 13 is in (10 0 , 12 0 )

13在(5,120)=> 13在(5,9)或13在(10,99)或13在(10,12 0)

After this second rewrite, it becomes a simple numeric check. Note that if you have the range 10,99 appear then you have all possible 2-digit prefixes and don't actually need to check, but that's an optimization. (I'm assuming we ignore prefixes 00-09)

在第二次重写之后，它变成了一个简单的数字检查。注意，如果你有10,99的范围，那么你就有了所有可能的2位数前缀，实际上不需要检查，但这是一个优化。(我假设我们忽略前缀00-09)

#10

Yes another answer. For input X and bounds MIN and MAX

是的另一个答案。输入X和边界最小值和最大值。

WHILE (X < MIN)
  IF X is a prefix of MIN
    x = 10*x + next digit of MIN
  ELSE
    x = 10*x
RETURN (x>= MIN && x<=MAX)

This works by "typing" the next lowest digit. So the hard case 13 in (135, 140) adds a 5 to produce 135, not a zero.

这可以通过“输入”下一个最低的数字来实现。所以硬的情况是13(135,140)加5得到135，而不是0。

#11

Whatever the implementation method you chose, you should consider building a lot of unit tests. Because you're asking the question just as you would have written a test for test-driven development (TDD). So I suggest that, while you are waiting for a suitable algorithm to pop out of stack overflow, write your unit tests:

无论您选择什么实现方法，您都应该考虑构建大量的单元测试。因为您所问的问题就像您编写测试驱动开发(TDD)的测试一样。所以我建议，当您等待合适的算法跳出堆栈溢出时，编写单元测试:

Make your test fail if the examples you give don't yield the results in your examples. Write a couple of other limit test cases just to be sure. Then, if you happen to use a wrong or buggy algorithm, you will know it soon. Once your test passes, you'll know that you've reached your goal.

如果您给出的示例没有在示例中产生结果，则使您的测试失败。为了确定，编写几个其他的极限测试用例。然后，如果您碰巧使用了错误的或错误的算法，您很快就会知道。一旦你的测试通过，你就会知道你已经达到了你的目标。

Plus, it shields you from any regression in the future

另外，它可以让你避免将来的任何回归

#12

Maybe I'm under-thinking this but assuming that the Min-Max range of integers are all positive (i.e. greater than or equal to zero), this code block should do the trick nicely:

也许我没考虑到这一点，但假设整数的最小-最大值范围都是正的(即大于或等于零)，这个代码块就能很好地完成这个任务:

bool CheckRange(int InputValue, int MinValue, int MaxValue)
{
    // Assumes that:
    //    1. InputValue >= MinValue 
    //    2. MinValue >= 0
    //    3. MinValue <= MaxValue 
    //
    if (InputValue < 0)         // The input value is less than zero
        return false;
    //
    if (InputValue > MaxValue)  // The input value is greater than max value
        return false;
    //
    if (InputValue == 0 && InputValue < MinValue)
        return false;       // The input value is zero and less than a non-zero min value
    //
    int WorkValue = InputValue; // Seed a working variable
    //
    while (WorkValue <= MaxValue)
    {
        if (WorkValue >= MinValue && WorkValue <= MaxValue)
            return true; // The input value (or a stem) is within range
        else
            WorkValue *= 10; // Not in range, multiply by 10 to check stem again
    }
    //
    return false;
}

#13

OK, a bit late to the party, but here goes...

好吧，参加聚会有点晚了，但是……

Note that we're talking about user input here, so it's not sufficient to just // TODO: consider overflow. Validating user input is a war, and cutting corners will eventually lead to the detonation of an IED. (Well, ok, maybe not so dramatic, but still...) In fact, only one of the algorithms in ecatmur's useful test harness handles a corner case properly ({23, 2147483644, 2147483646, false}), and the test harness itself goes into an infinite loop if t.max is too big.

注意，我们这里讨论的是用户输入，所以仅仅// TODO是不够的:考虑溢出。验证用户输入是一场战争，偷工减料最终会导致简易爆炸装置的爆炸。(好吧，也许不是那么夸张，但是……)事实上，在ecatmur有用的测试指令中，只有一个算法能够正确地处理一个转角案例({23,2147483644,2147483646,false})，并且如果t，测试指令本身就会进入一个无限循环。马克斯太大了。

The only one which passed was ecatmur_in_range_div, which I think is quite nice. However, it is possible to make it (slightly) faster by adding a few checks:

唯一通过的是ecatmur_in_range_div，我认为它很不错。但是，可以通过增加一些检查使它(稍微)更快:

bool in_range_div(int input, int min, int max)
{
  if (input > max) return false;
  if (input >= min) return true;
  if (max / 10 >= min) return true;

  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

How much faster "depends"; it would be particularly useful if min and max were compile-time constants. The first two tests are obvious, I think; the third one can be proven in a variety of ways but the simplest is to just observe the behaviour of ecatmur's loop: when the loop ends, input is >= min but < 10*min, so if 10*min < max, input must be less than max.

快多少“取决于”;如果min和max是编译时常数，这将是非常有用的。我认为前两个测试很明显;第三种方法可以用多种方法证明，但最简单的方法是观察ecatmur循环的行为:当循环结束时，输入是>= min，但< 10*min，所以如果10*min < max，输入必须小于max。

Expressing the arithmetic in terms of division rather than multiplication ought to be a habit; I know that most of us grew up with the idea that division is sloooooow and must be avoided. However, division, unlike multiplication, will not overflow. Indeed, whenever you find yourself writing:

用除法而不是乘法来表示算术应该是一种习惯;我知道，我们大多数人在成长过程中都有这样一种想法，那就是，分工是空洞的，必须避免。然而，除法不同于乘法，它不会溢出。的确，每当你发现自己在写作:

if (a * k < b) ...

or

或

for (..., a < b, a *= k)

or other variations on those themes, you should immediately flag that as integer overflow, and change it to the equivalent division.

或者这些主题的其他变体，您应该立即将其标记为整数溢出，并将其更改为等效的除法。

Actually, the same goes for addition except in one important (but common) case:

事实上，加法也是一样的，除了一个重要的(但常见的)情况:

if (a + k < b) ...

or

或

a += k; if (a < b) ...

are also unsafe unless k is one, and you know that a < b before the addition. That exception lets the normal for loop work without too much thought. But watch out for this, which I used to use as part of an interview question:

也不安全，除非k是1，你知道a < b在加法之前。这个异常允许正常的for循环工作，而不需要考虑太多。但要注意这一点，我过去经常把它作为面试问题的一部分:

// enumerate every kth element of the range [a, b)
assert(a < b);
for (; a < b; a += k) { ... }

Sadly, very few candidates got it.

遗憾的是，很少有候选人能做到这一点。

#14

I would now delete this answer, except that it shows a failed approach.

我现在删除这个答案，除了它显示了一个失败的方法。

After checking Str(min).StartWith(input), you need to check numerically if any 10^n*Val(input) is within the range, as Ben Voight's current answer says.

检查后Str(min).StartWith(输入),您需要检查数字是否10 ^ n *瓦尔(输入)范围内,本•沃伊特目前的回答说。

---

Failed attempt

Edited because of Ben Voigt's comment: (I had missed his first point in his current answer: prefix matches to the minimum are OK.)

因为Ben Voigt的评论而编辑(我错过了他当前答案中的第一点:前缀匹配到最小值是OK的)。

My solution, based upon @Ben Voigt's insights, is check if Min StartsWith the current input. If not, PadRight the current input with 0 to the length of Max as a string. Then if this modified input is lexically (i.e. treated as strings) between Min and Max it's OK.

基于@Ben Voigt的见解，我的解决方案是检查Min是否启动当前输入。如果不是，则将当前输入以0到最大长度为字符串的方式填入。如果这个修改后的输入在Min和Max之间是按词法(即被当作字符串来处理)，那就可以了。

Pseudo code:

伪代码:

 Confirm input has only digits, striping leading 0s
    (most easily done by converting it to an integer and back to a string)

 check = Str(min).StartsWith(input)
 If Not check Then
   testInput = input.PadRight(Len(Str(max)), '0')
   check = Str(min) <= testInput && testInput <= Str(max)
 End If

#15

int input = 15;
int lower_bound = 1561;
int upper_bound = 1567;
int ipow = 0;
while (lower_bound > 0) {
    if (lower_bound > input) {
        ++ipow;
        lower_bound = lower_bound / 10;
    } else {
        int i = pow(10, ipow) * input;
        if (i < upper_bound) {
            return true;
        }
        return false;
    }
}
return false;