C语言 如何有效地计算整数类型的最小值和最大值?

vc9ivgsu  于 12个月前  发布在  其他
关注(0)|答案(5)|浏览(110)

练习2-1。写一个程序,通过从标准头打印适当的值和直接计算来确定char、short、int和long变量的范围,包括有符号和无符号的。如果你计算它们,难度更大:确定各种浮点类型的范围。
我已经为一些类型写了这段代码:

#include <stdio.h>

int main()
{
        int u;

        for (u = 1; u > 0; ++u);

        int l = u;
        --u;

        printf("int : %d and %d\n", l, u);

        char u_c;

        for (u_c = 1; u_c > 0; ++u_c);

        char l_c = u_c;
        --u_c;

        printf("char : %d and %d\n", l_c, u_c);

        short u_s;

        for (u_s = 1; u_s > 0; ++u_s);

        short l_s = u_s;
        --u_s;

        printf("short : %d and %d\n", l_s, u_s);
 
        return 0;
}

问题是,对于像int这样的大型类型,for循环需要5或6秒才能结束,有没有更好更有效的方法?

zlhcx6iw

zlhcx6iw1#

未定义行为

for (u = 1; u > 0; ++u);最终溢出,这是undefined behavior(UB),并且不是找到 signed integer类型限制的可靠方法。
查找 unsigned 类型的极限很容易。将-1分配给类型是一个快速的解决方案-并且定义良好。将超出范围的值转换为 unsigned 类型时会“回绕”。

假设有符号整数 * 类型及其对应的 * 无符号 * 类型具有相同数量的值+符号位(或等效的相同数量的填充位),并且 * 有符号整数 * 使用2的补码编码(C23需要),* 有符号 * 类型的最大值大约是 * 无符号 * 类型的一半。

shortlong也是如此。
样本代码:

#include <stdio.h>

void calculate_integer_type_range(void) {
  unsigned char uc = (unsigned char) -1;
  printf("unsigned char       0 to %hhu\n", uc);
  unsigned u = (unsigned) -1;
  printf("unsigned            0 to %u\n", u);
  unsigned long long ull = (unsigned long long) -1;
  printf("unsigned long long  0 to %llu\n", ull);

  printf("\nAssuming: 2's complement and no padding.\n\n");

  signed char sc = (signed char) (uc/2);
  printf("signed char         %hhd to %hhd\n", -sc - 1, sc);
  int i = (int) (u/2);
  printf("int                 %d to %d\n", -i - 1, i);
  long long ll = (long long) (ull/2);
  printf("long long           %lld to %lld\n", -ll - 1, ll);

  // char is a little tricky as we first need to determine if it is signed.
  if ((char)-1 < 0) {
    char c = (char) (uc/2);
    printf("char                %hhd to %hhd\n", -c - 1, c);
  } else {
    char c = (char) -1;
    printf("char              0 to %hhu\n", c);
  }
}

输出

unsigned char       0 to 255
unsigned            0 to 4294967295
unsigned long long  0 to 18446744073709551615

Assuming: 2's complement and no padding.

signed char         -128 to 127
int                 -2147483648 to 2147483647
long long           -9223372036854775808 to 9223372036854775807
char                -128 to 127
u59ebvdq

u59ebvdq2#

左移或乘以2会快得多。例如,您的上限范围为:

for (u = 1; u > 0; u <<= 1);
u--;

参见:https://onlinegdb.com/m9q3Xao1y
注意,有符号溢出是未定义的行为。

kjthegm6

kjthegm63#

你应该能够避免所有的循环,只使用一些位/数学运算。这假设理解2's complement数字是如何存储的:

// set all bits
unsigned char v = ~0;

// strip off the most significant bit
char max = v >> 1;

// wrap around
char min = max + 1;

printf("%d == %d\n", min, max);
slwdgvem

slwdgvem4#

#include <limits.h>是正确答案。
否则,您可以在编译时手动生成相同的常量,而无需任何开销,只要给出一些假设:

  • 代码运行在一个有用的,现实世界的计算机上。
  • 有用的,真实世界的计算机是那些使用2的补码,8位字节,没有填充或陷阱表示。
  • 无符号到有符号的转换不会产生意外的行为,例如引发信号。
#include <stdio.h>

int main(void)
{
  int int_max = ( 1u << (sizeof(int)*8 - 1) ) - 1;
  printf("%d\n", int_max);
  int int_min = ( 1u << (sizeof(int)*8 - 1) );
  printf("%d\n", int_min);

  short short_max = ( 1u << (sizeof(short)*8 - 1) ) - 1;
  printf("%hd\n", short_max);
  short short_min = ( 1u << (sizeof(short)*8 - 1) );
  printf("%hd\n", short_min);

  long long_max = ( 1ul << (sizeof(long)*8 - 1) ) - 1;
  printf("%ld\n", long_max);
  long long_min = ( 1ul << (sizeof(long)*8 - 1) );
  printf("%ld\n", long_min);
}

说明:
通过将一个无符号的1u移位,使其比类型中可用的总位数少一位,我们将MSB设置为1。在2的补码计算机上,只有MSB集的数字给出了类型的最小数字,一旦转换为正确的有符号类型。类似地,MSB设置为减1的数给出最大数。
gcc 13.2 x86_64上的输出:

2147483647
-2147483648
32767
-32768
9223372036854775807
-9223372036854775808

反汇编看起来像mov esi, 2147483647等等,一切都是在编译时预先计算的。
8可以和CHAR_BITS交换,但是如果你有权限访问limits.h,你就不会手动做这样愚蠢的事情了。

rjee0c15

rjee0c155#

问题是,对于像int这样的大型类型,for循环需要5或6秒才能结束,有没有更好更有效的方法?
那么,对于int,你可以数到2,147,483,647次。这是20亿次增量操作,在5- 6秒内完成这些操作是一个很好的打击!!!
没有更好的方法来计数到2^31 - 1,而不是直接计数。但这只是如果你想通过计数得到最高值**。**只要继续阅读。

首先说明:

有符号溢出(这已经在其他一些答案中提到过)意味着未定义的行为。(下面描述的signedunsigned的方法,甚至可能适用于你,在某个时候,得到一个U. B。)在K&R编写的时候,即使在它的第二版中,也不是这样的,它涵盖了第一个可用的ANSI-C规范。一旦给定,我们可以使用两种方法来追求计算最大值和最小值的目标:
1.使用一些特定的架构。在K&R写作的时候,最常见的C编译器架构是DEC PDP-11(有几种大小和风格),它支持16位二进制补码运算。
1.保持实际的标准和处理U.B.这两种方法都有问题,使您无法确定当今计算机中某些类型的最大/最小值。
我会尽量给你给予一些东西,在我看来,这将使你得到一些有用的在大多数情况下。

一种可能的方式

如果你想得到一个整数的最大值计算它...你可以从1(或-1)开始,并将其加倍,直到你得到一个不大于(或小于,对于负数)前一个数字的数字。这意味着你已经越过了UB的边界线。当你接近任何一边时,你都会有一个严格的递增/递减序列,给你适合类型的数字,直到你越过边界。在这种情况下,前一个号码将是一个这样的候选人成为目标(尚未完成)。一个比你遵循的方法更好的方法,递增数字直到你得到最终的目标是通过加倍它们,因为你只需要32次溢出一个32位的数字和128次循环就可以得到一个128位的数字。乘以2就可以了,对于正数和负数(在书中的任何地方,两种位逻辑和算术,表明K&R隐含地假设正在使用2的补码,我特意编辑了这个答案,从不包括位逻辑运算符,所以不包括对数字的位表示的依赖-即使你可以使用不同于2的乘法因子,例如10,但这会使速度变慢一点)
一旦你得到一个不大于前一个的数(当然,最大数不能再加倍,或者新的数将是最大值,所以我可以完美地假设,即使在U. B的情况下,这是一个很好的方法。(这是因为我们用以前的号码到U.B.并且永远不会有溢出的结果),我们将不会得到U. B。乘以2可以给予你一个最终的目标(记住,目标是U.B.的前一个)现在你可以保存你的数字的副本,并尝试添加,每次一个值除以相同的数字(在这种情况下是2),因为它是乘以之前,并将该数字添加到目标获得的值,看看我们是否得到一个新的目标比你以前的大(我们总是保持最新的有效目标,这将是请求的最大/最小值)。在你把这个数字除以2足够多次后,得到1(记住这个数字总是2的幂,所以它总是能被2整除,直到你得到最后的1),你会得到一个更大的数字,当只加1时会产生溢出,所以这将是你的实现中可用的最大值。
这个算法会在哪里失败?在程序处于未知状态的情况下(例如:引发异常)将使算法在第一个U. B之后失败。否则,所有的计算都将使用正确和精细的值,并且在增长的情况下需要将数字加倍最多30次,并且对于32位有符号的数字,需要另外最多29次加法。

保证金注解

我不知道否决的原因,但答案是(可能我犯了一些语言错误,我不是说英语的人)基本上是正确的,基于K&R中发布的原始练习中所述的资源可用性(任何版本,因为第二版只包含ANSI-C语言的扩展,但文本和练习保持不变),假定给定的上下文(对于像INT_MAX之类的常量,不能访问<limits.h>)我第一次看到这个问题的时候就意识到了这个问题的真正意图,大约在1979年,那就是处理那些不清楚计算机结果会给你给予什么的情况,不应该让你害怕面对这样的问题。
无论如何,对答案的评论将不胜感激,以便编辑/改进答案或纠正表达。帮助者惩罚永远不应该是帮助意图的一种选择。提前感谢您允许我保留此说明(这意味着,请不要删除它)无论如何,我不会发布代码来实现上面的算法,以保留作业的意图。

相关问题