查看数字是否小于 2^32
See if number is smaller than 2^32
我正在通过标准输入读取大量数字，我需要找到它，如果数字在 [0,2^32] 范围内（可能是 2^32-1，我不确定那个），所以它也不接受负数。还有一些情况是数字以数百个 null 开头，我需要忽略这些情况。
我确定如果我在数据类型上做错了什么，目前我使用“long”作为数据类型，因为我认为这总是最大为 2^32。所以如果有溢出，我得到一个负数，我可以证明 long 是否小于 0。
但是现在我意识到long的大小也取决于计算机的系统。
有没有人可以告诉我应该选择哪种数据类型和操作来证明这一点？
起始数据类型只是一个字符指针。
这取决于你的具体情况。如果您的应用程序正在读取完全任意的输入，那么您将需要对传入的文本进行一些预处理。此时您可以检测减号（并拒绝输入）并且您可以去除前导零。
之后，您可以轻松检查数字字符串的长度，如果它超过 10 位（2^32 = 4294967296 有 10 位）则拒绝输入。如果它短于 10 位数字，那么您知道它在 [0..2^32-1] 范围内。
如果正好有 10 个数字，那么您至少有几个选择：
- 解析成大于32位的整数（如64位类型）直接判断是否为
< 2^32
- 一个字符一个字符地读取它，将它与 2^32 的数字进行比较。这可以通过执行字符串
cmp. 轻松实现
您使用哪一个取决于您的限制。
我建议使用 int64_t 以确保您的号码在每个架构上都具有相同的大小。您将有 2^32 "positive or null" 个数字，任何低于零的数字都是溢出或负数（只有真正的负数会再次变为正数）。但是你可以通过将符号读作字符而不是数字读作 int64_t 来规避这种情况，所以任何负数都会溢出（因为你之前抓住了'-'符号）
这是'PSEUDO-code'来说明这个过程：
char sign = '[=10=]'
uint64_t = 0
read (%c,&sign)
if (c=='-' or c=='+' or isdigit(c))
if isdigit(c)
unget()
read(%ull, &number) //read as unsigned as only negative are 2-complement
if number < 0
// the number is too big
else
//number is < 2^32
else
// number is "truly" negative
您无法通过使用 32 位数字来检测 32 位数字的溢出。如果它是无符号的，它将始终被理解为 0 到 2^32 -1 之间的数字。溢出的输入仍然会导致有效的输出。带符号的 32 位值将是 "valid"，范围为 0 - 2^31-1。负值你会被认为是无效的。在 -2^31 和 0 或 2^31 和 2^32-1 之间的 over/under 流动输入将导致无效的负数。但是，您可能会发现 2^32 以上的数字会再次显示为有效。我建议您使用带符号的 64 位数字并将负数或大数视为无效输入。这为您提供了可以正确过滤的更大范围的输入值。例如，如果输入是逗号限制的并且省略了逗号，则仍然可能存在问题。我建议作为字符串的输入数字不应超过限制长度。长度过滤器应允许表示大于 2^32 的数字的字符串，但应过滤掉大于 2^63 的数字。在中间的某个地方。要测试类型的大小，请使用 "sizeof()"。例如 sizeof(long)、sizeof(long long) 等。然而，您的平台通常有明确大小的整数。为了可移植性，使用您自己的类型并使用 typedef，并将依赖于平台的代码本地化到专用于平台依赖性的包含文件中。
它比第一眼看上去要棘手一些。原因是当您允许任意长的输入序列时，您甚至可能超过可用的最大数据类型，例如，即使是 64 位也可能太少。
根据您用于读取数字的方法，是否检测到数据类型溢出。例如，如果处理后的整数值不适合无符号长整型，scanf("%lu",...) 可能会导致未定义的行为（例如，参见这个关于 scanf 的在线 c11 草案）：
10 ... If this object does not have an appropriate type, or if the
result of the conversion cannot be represented in the object, the
behavior is undefined.
所以不要使用scanf进行任意输入。
相比之下，函数 strtoul 具有定义的溢出行为（再次来自在线 c11 草案，涉及 strtol）：
8) The strtol, strtoll, strtoul, and strtoull functions return the
converted value, if any. If no conversion could be performed, zero is
returned. If the correct value is outside the range of representable
values, LONG_MIN, LONG_MAX, LLONG_MIN, LLONG_MAX, ULONG_MAX, or
ULLONG_MAX is returned (according to the return type and sign of the
value, if any), and the value of the macro ERANGE is stored in errno.
你可以使用 strtol 因为它会给你一个至少有 32 位的数字，它告诉你溢出。如果long是64位，你can/need来区分一般溢出还是32位溢出。请参阅以下代码说明这一点：
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
void convert(const char* numStr) {
errno=0;
long num = strtol(numStr,NULL,10);
if (errno == ERANGE){
printf("numstr %s is out of long's range, which is %ld..%ld\n", numStr, LONG_MIN,LONG_MAX);
} else if (num < 0) {
printf("numstr %s is negative.\n", numStr);
} else if (num > UINT32_MAX) {
printf("numstr %s is out of 32 bit range, which is 0..%u\n", numStr, UINT32_MAX);
} else {
printf("OK; numstr %s is in 32 bit range, which is 0..%u\n", numStr, UINT32_MAX);
}
}
int main() {
convert("123456789012345678901234567890");
convert("-123");
convert("1234567890123567");
convert("32452345");
convert("0000000000000000000000032452345");
}
输出：
numstr 123456789012345678901234567890 is out of long's range, which is -9223372036854775808..9223372036854775807
numstr -123 is negative.
numstr 1234567890123567 is out of 32 bit range, which is 0..4294967295
OK; numstr 32452345 is in 32 bit range, which is 0..4294967295
OK; numstr 0000000000000000000000032452345 is in 32 bit range, which is 0..4294967295
您可以对 [0, 232-1] 范围（含）使用标准 strtoul() 函数。
我建议检查指针 strtoul() 分配（下面的 ends）以检测像 "O"（字母 O，非零）和 "1O"（一和字母 O，不是十）；即，输入确实有一个十进制数，并以合适的分隔符或字符串结束标记结束。
例如：
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>
const char *next_u32(const char *from, uint32_t *to)
{
const char *ends = from;
unsigned long value;
if (!from) {
errno = EINVAL; /* NULL from pointer */
return NULL;
}
/* Parse the number to 'value' */
errno = 0;
value = strtoul(from, (char **)ends, 10); /* 10 = decimal input */
if (errno)
return NULL;
if (ends == from) {
errno = EDOM; /* Not a valid number */
return NULL;
}
/* Is it too large? */
if (value > 4294967295uL) {
errno = ERANGE; /* Out of valid range */
return NULL;
}
/* Verify the separator is a space or end-of-string. */
if (*ends != '[=10=]' && *ends != '\t' && *ends != '\n' &&
*ends != '\v' && *ends != '\f' && *ends != '\r' &&
*ends != ' ') {
errno = EDOM; /* The number was immediately followed by garbage. */
return NULL;
}
/* Accepted. Save value, and return the pointer to the
first unparsed character. */
if (to)
*to = (uint32_t)value;
return ends;
}
要解析一行中的所有 32 位无符号整数，可以使用循环：
const char *line; /* Contains the line with decimal integers to parse */
uint32_t value;
while ((line = next_u32(line, &value))) {
/* Use 'value' */
}
如果您要解析大量十进制无符号整数，标准库的 strtoul() 并不是最快的选择。
此外，有时只对输入文件进行内存映射并让 OS 处理分页会更容易。然而，在那种情况下，末尾没有字符串结束 NUL 字节 ([=19=])，因此需要使用不同的接口。
对于这些情况，您可以使用以下功能。它获取并更新指向内容中当前位置的指针，但永远不会超过结束指针。如果输入中的下一项是十进制 32 位无符号整数，则它 returns 为零，否则为非零错误代码。
#define NEXT_OK 0
#define NEXT_END 1
#define NEXT_BAD -1
#define NEXT_OVER -2
static int next_u32(const char **fromptr, const char *end,
uint32_t *to)
{
const char *from;
uint32_t val = 0;
if (!fromptr)
return NEXT_END;
from = *fromptr;
/* Skip whitespace characters, including NUL bytes. */
while (from < end && (*from == '[=12=]' || *from == '\t' ||
*from == '\n' || *from == '\v' ||
*from == '\f' || *from == '\r' ||
*from == ' '))
from++;
/* At end? */
if (from >= end)
return NEXT_END;
/* Skip a leading + sign. */
if (*from == '+' && end - from > 1)
from++;
/* Must be a decimal digit now. */
if (!(*from >= '0' && *from <= '9'))
return NEXT_BAD;
/* Skip leading zeroes. */
while (from < end && *from == '0')
from++;
/* Parse the rest of the decimal number, if any. */
while (from < end && *from >= '0' && *from <= '9') {
if ((value > 429496729) || (value == 429496729 && *from >= '6'))
return NEXT_OVER;
value = (10 * value) + (*(from++) - '0');
}
/* If not at end, check the character. */
if (from < end && *from != '[=12=]' && *from != '\t' &&
*from != '\n' && *from != '\v' &&
*from != '\f' && *from != '\r' &&
*from != ' ')
return NEXT_BAD;
/* Parsed correctly. */
*fromptr = from;
if (*to)
*to = value;
return NEXT_OK;
}
我正在通过标准输入读取大量数字，我需要找到它，如果数字在 [0,2^32] 范围内（可能是 2^32-1，我不确定那个），所以它也不接受负数。还有一些情况是数字以数百个 null 开头，我需要忽略这些情况。 我确定如果我在数据类型上做错了什么，目前我使用“long”作为数据类型，因为我认为这总是最大为 2^32。所以如果有溢出，我得到一个负数，我可以证明 long 是否小于 0。 但是现在我意识到long的大小也取决于计算机的系统。
有没有人可以告诉我应该选择哪种数据类型和操作来证明这一点？ 起始数据类型只是一个字符指针。
这取决于你的具体情况。如果您的应用程序正在读取完全任意的输入，那么您将需要对传入的文本进行一些预处理。此时您可以检测减号（并拒绝输入）并且您可以去除前导零。
之后，您可以轻松检查数字字符串的长度，如果它超过 10 位（2^32 = 4294967296 有 10 位）则拒绝输入。如果它短于 10 位数字，那么您知道它在 [0..2^32-1] 范围内。
如果正好有 10 个数字，那么您至少有几个选择：
- 解析成大于32位的整数（如64位类型）直接判断是否为
< 2^32 - 一个字符一个字符地读取它，将它与 2^32 的数字进行比较。这可以通过执行字符串
cmp. 轻松实现
您使用哪一个取决于您的限制。
我建议使用 int64_t 以确保您的号码在每个架构上都具有相同的大小。您将有 2^32 "positive or null" 个数字，任何低于零的数字都是溢出或负数（只有真正的负数会再次变为正数）。但是你可以通过将符号读作字符而不是数字读作 int64_t 来规避这种情况，所以任何负数都会溢出（因为你之前抓住了'-'符号）
这是'PSEUDO-code'来说明这个过程：
char sign = '[=10=]'
uint64_t = 0
read (%c,&sign)
if (c=='-' or c=='+' or isdigit(c))
if isdigit(c)
unget()
read(%ull, &number) //read as unsigned as only negative are 2-complement
if number < 0
// the number is too big
else
//number is < 2^32
else
// number is "truly" negative
您无法通过使用 32 位数字来检测 32 位数字的溢出。如果它是无符号的，它将始终被理解为 0 到 2^32 -1 之间的数字。溢出的输入仍然会导致有效的输出。带符号的 32 位值将是 "valid"，范围为 0 - 2^31-1。负值你会被认为是无效的。在 -2^31 和 0 或 2^31 和 2^32-1 之间的 over/under 流动输入将导致无效的负数。但是，您可能会发现 2^32 以上的数字会再次显示为有效。我建议您使用带符号的 64 位数字并将负数或大数视为无效输入。这为您提供了可以正确过滤的更大范围的输入值。例如，如果输入是逗号限制的并且省略了逗号，则仍然可能存在问题。我建议作为字符串的输入数字不应超过限制长度。长度过滤器应允许表示大于 2^32 的数字的字符串，但应过滤掉大于 2^63 的数字。在中间的某个地方。要测试类型的大小，请使用 "sizeof()"。例如 sizeof(long)、sizeof(long long) 等。然而，您的平台通常有明确大小的整数。为了可移植性，使用您自己的类型并使用 typedef，并将依赖于平台的代码本地化到专用于平台依赖性的包含文件中。
它比第一眼看上去要棘手一些。原因是当您允许任意长的输入序列时，您甚至可能超过可用的最大数据类型，例如，即使是 64 位也可能太少。
根据您用于读取数字的方法，是否检测到数据类型溢出。例如，如果处理后的整数值不适合无符号长整型，scanf("%lu",...) 可能会导致未定义的行为（例如，参见这个关于 scanf 的在线 c11 草案）：
10 ... If this object does not have an appropriate type, or if the result of the conversion cannot be represented in the object, the behavior is undefined.
所以不要使用scanf进行任意输入。
相比之下，函数 strtoul 具有定义的溢出行为（再次来自在线 c11 草案，涉及 strtol）：
8) The strtol, strtoll, strtoul, and strtoull functions return the converted value, if any. If no conversion could be performed, zero is returned. If the correct value is outside the range of representable values, LONG_MIN, LONG_MAX, LLONG_MIN, LLONG_MAX, ULONG_MAX, or ULLONG_MAX is returned (according to the return type and sign of the value, if any), and the value of the macro ERANGE is stored in errno.
你可以使用 strtol 因为它会给你一个至少有 32 位的数字，它告诉你溢出。如果long是64位，你can/need来区分一般溢出还是32位溢出。请参阅以下代码说明这一点：
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
void convert(const char* numStr) {
errno=0;
long num = strtol(numStr,NULL,10);
if (errno == ERANGE){
printf("numstr %s is out of long's range, which is %ld..%ld\n", numStr, LONG_MIN,LONG_MAX);
} else if (num < 0) {
printf("numstr %s is negative.\n", numStr);
} else if (num > UINT32_MAX) {
printf("numstr %s is out of 32 bit range, which is 0..%u\n", numStr, UINT32_MAX);
} else {
printf("OK; numstr %s is in 32 bit range, which is 0..%u\n", numStr, UINT32_MAX);
}
}
int main() {
convert("123456789012345678901234567890");
convert("-123");
convert("1234567890123567");
convert("32452345");
convert("0000000000000000000000032452345");
}
输出：
numstr 123456789012345678901234567890 is out of long's range, which is -9223372036854775808..9223372036854775807
numstr -123 is negative.
numstr 1234567890123567 is out of 32 bit range, which is 0..4294967295
OK; numstr 32452345 is in 32 bit range, which is 0..4294967295
OK; numstr 0000000000000000000000032452345 is in 32 bit range, which is 0..4294967295
您可以对 [0, 232-1] 范围（含）使用标准 strtoul() 函数。
我建议检查指针 strtoul() 分配（下面的 ends）以检测像 "O"（字母 O，非零）和 "1O"（一和字母 O，不是十）；即，输入确实有一个十进制数，并以合适的分隔符或字符串结束标记结束。
例如：
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>
const char *next_u32(const char *from, uint32_t *to)
{
const char *ends = from;
unsigned long value;
if (!from) {
errno = EINVAL; /* NULL from pointer */
return NULL;
}
/* Parse the number to 'value' */
errno = 0;
value = strtoul(from, (char **)ends, 10); /* 10 = decimal input */
if (errno)
return NULL;
if (ends == from) {
errno = EDOM; /* Not a valid number */
return NULL;
}
/* Is it too large? */
if (value > 4294967295uL) {
errno = ERANGE; /* Out of valid range */
return NULL;
}
/* Verify the separator is a space or end-of-string. */
if (*ends != '[=10=]' && *ends != '\t' && *ends != '\n' &&
*ends != '\v' && *ends != '\f' && *ends != '\r' &&
*ends != ' ') {
errno = EDOM; /* The number was immediately followed by garbage. */
return NULL;
}
/* Accepted. Save value, and return the pointer to the
first unparsed character. */
if (to)
*to = (uint32_t)value;
return ends;
}
要解析一行中的所有 32 位无符号整数，可以使用循环：
const char *line; /* Contains the line with decimal integers to parse */
uint32_t value;
while ((line = next_u32(line, &value))) {
/* Use 'value' */
}
如果您要解析大量十进制无符号整数，标准库的 strtoul() 并不是最快的选择。
此外，有时只对输入文件进行内存映射并让 OS 处理分页会更容易。然而，在那种情况下，末尾没有字符串结束 NUL 字节 ([=19=])，因此需要使用不同的接口。
对于这些情况，您可以使用以下功能。它获取并更新指向内容中当前位置的指针，但永远不会超过结束指针。如果输入中的下一项是十进制 32 位无符号整数，则它 returns 为零，否则为非零错误代码。
#define NEXT_OK 0
#define NEXT_END 1
#define NEXT_BAD -1
#define NEXT_OVER -2
static int next_u32(const char **fromptr, const char *end,
uint32_t *to)
{
const char *from;
uint32_t val = 0;
if (!fromptr)
return NEXT_END;
from = *fromptr;
/* Skip whitespace characters, including NUL bytes. */
while (from < end && (*from == '[=12=]' || *from == '\t' ||
*from == '\n' || *from == '\v' ||
*from == '\f' || *from == '\r' ||
*from == ' '))
from++;
/* At end? */
if (from >= end)
return NEXT_END;
/* Skip a leading + sign. */
if (*from == '+' && end - from > 1)
from++;
/* Must be a decimal digit now. */
if (!(*from >= '0' && *from <= '9'))
return NEXT_BAD;
/* Skip leading zeroes. */
while (from < end && *from == '0')
from++;
/* Parse the rest of the decimal number, if any. */
while (from < end && *from >= '0' && *from <= '9') {
if ((value > 429496729) || (value == 429496729 && *from >= '6'))
return NEXT_OVER;
value = (10 * value) + (*(from++) - '0');
}
/* If not at end, check the character. */
if (from < end && *from != '[=12=]' && *from != '\t' &&
*from != '\n' && *from != '\v' &&
*from != '\f' && *from != '\r' &&
*from != ' ')
return NEXT_BAD;
/* Parsed correctly. */
*fromptr = from;
if (*to)
*to = value;
return NEXT_OK;
}