检查整数是否位于给定 range/bounds 检查中的优化方法

Question

在 c 编程中查找是否有任何给定值位于范围内，if 条件如下使用。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define U_LIMIT     100
#define L_LIMIT    -100

int check_num(char *in)
{
    int i = 0;

    if (in[i] == '-' || in[i] == '+') {
        i++;
        if (in[i] == '[=11=]')
            return 0;
    }

    while (i < strlen(in)) {
        if(!isdigit(in[i]))
            return 0;
        i++;
    }
    return 1;
}

int main(int argc, char *argv[])
{
    int i;
    if (argc != 2)
       return 1;

    if (!check_num(argv[1])) {
       printf("Not a digit\n");
       return 1;
    }

    i = atoi(argv[1]);
    if (i < U_LIMIT && i > L_LIMIT)
       printf("Within Range\n");
    else
       printf("Outside Range\n");

    return 0;
}

示例输出：

./a.out 1    -> Within Range
./a.out 100  -> Outside Range
./a.out -100 -> Outside Range
./a.out -    -> Not a digit
./a.out e    -> Not a digit

我的问题是

Can the above program be optimized(for speed) further without loosing out any of the error check conditions?

Is there any other best optimized(for speed) method to solve for the same issue?

Answer 1

while (i < strlen(in))

既然你的问题是关于时间优化的，那么这里是你改进的部分

int n =strlen(in);

while(i<n){

通过这样做 strlen() 不会在每次迭代中计算，这很耗时。其余代码应该没问题，因为您正在使用 if() 检查更简单和最好的边界。

Answer 2

无需检查用户输入，然后对其进行解析。只需使用 sscanf 即可同时完成：

#include <stdio.h>

#define U_LIMIT     100
#define L_LIMIT    -100

int main(int argc, char *argv[])
{
    int i;

    if (argc != 2) {
        printf("Missing argument\n");
        return 1;
    }

    /* ALWAYS check the return value from scanf() and friends!
     * It returns the number of items in your format string successfully
     * assigned to. Make sure it matches the number of values you're
     * expecting, (one in this case).
     */
    if (sscanf(argv[1], "%d", &i) != 1) {
        printf("Invalid number\n");
        return 1;
    }

    /* Doesn't get any simpler than an if statement */
    if (i < U_LIMIT && i > L_LIMIT)
       printf("Within Range\n");
    else
       printf("Outside Range\n");

    return 0;
}

此外，不要在游戏初期尝试疯狂优化。专注于编写干净、简洁的代码，让优化编译器为您处理剩下的事情。

在 -O3 优化级别，GCC 为 main() 生成以下程序集。我只保留了关于整数比较的有趣部分。

GCC 命令行：gcc -Wall -Werror -O3 -g test.c

Objdump 命令行：objdump -d -Mintel -S a.out

if (i < U_LIMIT && i > L_LIMIT)
  4004e5:   mov    eax,DWORD PTR [rsp]
  4004e8:   add    eax,0x63
  4004eb:   cmp    eax,0xc6
  4004f0:   jbe    400500 <main+0x50>

注意编译器为您做了什么。它没有进行两次比较，而是先将 0x63 (99) 添加到 i，然后将该值与 0xC6 (198) 进行比较。这相当于：

if ((unsigned int)(i + 99) <= 198)

这样，只需要一个条件分支。最酷的部分是它进行无符号比较。如果 i 小于 -100，那么 (i + 99) 仍然是负数，并且被解释为无符号整数是 0xfffffed3（一个非常大的数字），它是 而不是 <= 198.

最好的部分是什么？你想都不用想！

Answer 3

选项 strtol()

您可能只想使用 strtol(3):

long int strtol(const char *nptr, char **endptr, int base);

The strtol() function converts the initial part of the string in 
nptr to a long integer value according to the given base, which 
must be between 2 and 36 inclusive, or be the special value 0.

此外：如果输入数据上溢或下溢，您将得到一个 return 值。

此外：该函数会将 endptr 放置到第一个 'invalid' 字符。

char*     in = "123a";
size_t   len = strlen(in);
char*    end = NULL;
long int out = strtol(in, &end, 10);

if (out == LONG_MIN || out == LONG_MAX) {
    // underflow || overflow
} else if (in + len < end) {
    // invalid chars while parsing
} else {
    // ok
}

选项 sscanf()

标准的替代方法是使用 sscanf()，这通常没问题，但当您需要解析大量整数时可能会成为瓶颈（重新解析格式字符串是一个问题）。

选项 rollyourown()

因为你已经自己检查了，所以你最好自己做解析（取自 scan_ulong.c of qmail）：

unsigned int scan_ulong(const char *s, unsigned long *u) {
    unsigned int pos = 0;
    unsigned long result = 0;
    unsigned long c;
    while ((c = (unsigned long) (unsigned char) (s[pos] - '0')) < 10) {
        result = result * 10 + c;
        ++pos;
    }

    if (u) {
        *u = result;
    }
    return pos;
}

这一段相当于您的 isdigit() 代码，但同时解析数字。如果解析数字是您项目的速度问题，请考虑选项 strtol()（取决于您使用的编译器/平台）或 scan_ulong() 变体，否则请坚持使用 sscanf()。

检查整数是否位于给定 range/bounds 检查中的优化方法

Optimized method to check if an integer lies in the given range/bounds check

c

linux