9

这个相关问题是关于在编译时确定有符号类型的最大值：

C题：off_t（和其他有符号整数类型）的最小值和最大值

但是，我已经意识到在运行时time_t确定带符号类型（例如or off_t）的最大值似乎是一项非常困难的任务。

我能想到的最接近解决方案的是：

uintmax_t x = (uintmax_t)1<<CHAR_BIT*sizeof(type)-2;
while ((type)x<=0) x>>=1;

只要type没有填充位，这就会避免任何循环，但如果type确实有填充位，则强制转换会调用实​​现定义的行为，这可能是一个信号或无意义的实现定义的转换（例如剥离符号位）。

我开始认为这个问题是无法解决的，这有点令人不安，在我看来，这将是 C 标准中的一个缺陷。有什么想法可以证明我错了吗？

4

12 回答 12

4

让我们先看看 C 是如何定义“整数类型”的。取自ISO/IEC 9899，§6.2.6.2：

6.2.6.2 整数类型
1
对于 unsigned char 以外的无符号整数类型，对象表示的位应分为两组：值位和填充位（后者不需要任何一个）。如果有 N 个值位，则每个位应表示 1 和 2N-1 之间的 2 的不同幂，以便该类型的对象应能够使用纯二进制表示表示从 0 到 2N-1 的值；这应称为值表示。未指定任何填充位的值。44)
2
对于有符号整数类型，对象表示的位应分为三组：值位、填充位和符号位。不需要任何填充位；应该只有一个符号位。作为值位的每个位应与相应无符号类型的对象表示中的相同位具有相同的值（如果有符号类型中有 M 个值位，无符号类型中有 N 个值位，则 M ≤ N）。如果符号位为零，则不应影响结果值。如果符号位为 1，则该值应通过以下方式之一进行修改：

— 符号位为 0 的对应值取反（符号和幅度）；
— 符号位的值为 -(2N)（二进制补码）；
— 符号位的值为 −(2N − 1)（反码）。

其中哪个适用是实现定义的，符号位为 1 且所有值位为零（对于前两个）或符号位和所有值位为 1（对于一个补码）的值是否是陷阱表示或正常值。在符号和幅度以及一个的补码的情况下，如果这个表示是一个正常值，它被称为负零。

因此我们可以得出以下结论：

  • ~(int)0可能是陷阱表示，即将所有位设置为是一个坏主意
  • 中可能int有对其值没有影响的填充位
  • 实际表示 2 次方的位的顺序是未定义的；符号位的位置也是如此，如果它存在的话。

好消息是：

  • 只有一个符号位
  • 只有一位代表值 1


考虑到这一点，有一种简单的技术可以找到int. 找到符号位，然后将其设置为 0 并将所有其他位设置为 1。

我们如何找到符号位？考虑int n = 1;，它是严格正的，并保证只有一位，可能还有一些填充位设置为 1。然后对于所有其他位i，如果为i==0真，则将其设置为 1 并查看结果值是否为负。如果不是，则将其恢复为 0。否则，我们找到了符号位。

现在我们知道了符号位的位置，我们将我们的int n，将符号位设置为 0，将所有其他位设置为 1，然后，我们就有了最大可能int值。

确定int 最小值稍微复杂一些，留给读者作为练习。



请注意，幽默的 C 标准并不要求两个不同int的 s 表现相同。如果我没记错的话，可能有两个不同的int对象，例如它们各自的符号位在不同的位置。



编辑：在与 R.. 讨论这种方法时（见下面的评论），我已经确信它在几个方面存在缺陷，更一般地说，根本没有解决方案。我看不到修复这个帖子的方法（除了删除它），所以我让它保持不变，以便下面的评论有意义。

于 2011-04-21T13:19:31.727 回答
3

更新：谢天谢地，我之前的回答是错误的，并且似乎有解决这个问题的方法。

intmax_t x;
for (x=INTMAX_MAX; (T)x!=x; x/=2);

该程序要么产生x包含 type 的最大可能值T，要么生成实现定义的信号。

解决信号情况可能是可能的，但困难且计算上不可行（因为必须为每个可能的信号编号安装信号处理程序），所以我认为这个答案并不完全令人满意。POSIX 信号语义可能会提供足够的附加属性以使其可行；我不知道。

有趣的部分，特别是如果您愿意假设您不在会生成信号的实现上，那么当(T)x导致实现定义的转换时会发生什么。上述循环的诀窍在于它完全不依赖于实现对转换值的选择。它所依赖的(T)x==x只是当且仅当x适合 type时才有可能T，因为否则 的值x超出了任何type表达式T的可能值范围。

老想法，错了，因为它没有考虑到上述(T)x==x属性：

我想我有一个证据的草图，证明我正在寻找的东西是不可能的：

  1. 让 X 成为符合 C 的实现并假设INT_MAX>32767.
  2. 定义一个与 X 相同的新 C 实现 Y，但其中 和 的值INT_MAX均INT_MIN除以 2。
  3. 证明 Y 是符合 C 的实现。

本大纲的基本思想是，由于与带符号类型的越界值相关的一切都是实现定义或未定义的行为，因此可以考虑任意数量的有符号整数类型的高值位作为填充位，除了limits.h.

关于这听起来是正确的还是虚假的有什么想法吗？如果它是正确的，我很乐意将赏金奖励给能够做得最好的人，使其更加严格。

于 2011-04-23T00:58:50.643 回答
3

在数学上，如果你有一个有限集（X，大小为 n（na 正整数）和一个比较运算符（X 中的 x,y,z；x<=y 和 y<=z 意味着 x<=z），它是找到最大值的非常简单的问题。（同样，它存在。）

解决这个问题的最简单方法，但计算量最大，是生成一个包含所有可能值的数组，然后找到最大值。

第 1 部分。对于具有有限成员集的任何类型，都有有限数量的位 (m) 可用于唯一地表示该类型的任何给定成员。我们只是创建一个包含所有可能的位模式的数组，其中任何给定的位模式都由特定类型中的给定值表示。

第 2 部分。接下来我们需要将每个二进制数转换为给定的类型。这个任务是我缺乏编程经验的地方，让我无法谈论如何完成这个任务。我读过一些关于铸造的文章，也许这会奏效？或者其他一些转换方法？

第 3 部分。假设上一步已完成，我们现在拥有所需类型的有限值集和该集上的比较运算符。找到最大值。

但如果...

...我们不知道给定类型的成员的确切数量？比我们高估了。如果我们不能产生合理的高估，那么这个数字应该有物理界限。一旦我们有一个高估，我们检查所有这些可能的位模式，以确认哪些位模式代表该类型的成员。在丢弃那些未使用的之后，我们现在有一组所有可能的位模式，它们代表给定类型的某些成员。这个最近生成的集合是我们现在在第 1 部分中使用的。

...我们没有那种类型的比较运算符？比具体问题不仅不可能，而且在逻辑上不相干。也就是说，如果我们的程序无法获得有意义的结果，如果我们比较来自给定类型的两个值，那么我们给定的类型在我们的程序上下文中没有排序。没有排序，就没有最大值。

...我们不能将给定的二进制数转换为给定的类型？然后方法中断。但与前面的例外类似，如果您不能转换类型，那么我们的工具集在逻辑上似乎非常有限。

从技术上讲，您可能不需要在二进制表示和给定类型之间进行转换。转换的重点是确保生成的列表是详尽的。

...我们想优化问题？比我们需要一些关于给定类型如何从二进制数映射的信息。例如，无符号整数、有符号整数（2 的补语）和有符号整数（1 的补语）每个都以非常有文档且简单的方式从位映射到数字。因此，如果我们想要 unsigned int 的最大可能值并且我们知道我们正在使用 m 位，那么我们可以简单地用 1 填充每个位，将位模式转换为十进制，然后输出数字。

这与优化有关，因为该解决方案最昂贵的部分是列出所有可能的答案。如果我们对给定类型如何从位模式映射有一些先前的知识，我们可以通过生成所有潜在候选来生成所有可能性的子集。

祝你好运。

于 2011-04-27T00:55:22.513 回答
1

我可能只是在这里写一些愚蠢的东西，因为我对 C 比较陌生，但这对于获得 a 的最大值不起作用signed吗？

unsigned x = ~0;
signed y=x/2;

这可能是一种愚蠢的做法，但据我所知，unsigned max值为signed max*2+1。它不会向后工作吗？

如果这被证明是完全不充分和不正确的，我们很抱歉浪费了时间。

于 2012-06-12T21:22:33.577 回答
0

不应该像下面的伪代码那样做这项工作吗？

signed_type_of_max_size test_values =
    [(1<<7)-1, (1<<15)-1, (1<<31)-1, (1<<63)-1];

for test_value in test_values:
    signed_foo_t a = test_value;
    signed_foo_t b = a + 1;
    if (b < a):
        print "Max positive value of signed_foo_t is ", a

或者更简单，为什么以下工作不应该？

signed_foo_t signed_foo_max = (1<<(sizeof(signed_foo_t)*8-1))-1;

不过，对于我自己的代码，我肯定会进行定义预处理器宏的构建时检查。

于 2011-01-27T05:42:07.523 回答
0

假设修改填充位不会创建陷阱表示，您可以使用 anunsigned char *循环并翻转各个位，直到您遇到符号位。如果您的初始值为~(type)0，这应该为您提供最大值：

type value = ~(type)0;
assert(value < 0);

unsigned char *bytes = (void *)&value;
size_t i = 0;
for(; i < sizeof value * CHAR_BIT; ++i)
{
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
    if(value > 0) break;
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
}

assert(value != ~(type)0);
// value == TYPE_MAX
于 2011-01-27T09:49:31.403 回答
0

由于您允许在运行时执行此操作，因此您可以编写一个事实上执行迭代左移的函数(type)3。如果您在值低于 时停止0，这将永远不会给您一个陷阱表示。迭代次数 - 1 将告诉您符号位的位置。

仍然是左移的问题。由于只使用运算符<<会导致溢出，这将是未定义的行为，因此我们不能直接使用运算符。

最简单的解决方案不是3像上面那样使用移位，而是迭代位位置并始终添加最低有效位。

type x;
unsigned char*B = &x;
size_t signbit = 7;
for(;;++signbit) {
  size_t bpos = signbit / CHAR_BIT;
  size_t apos = signbit % CHAR_BIT;
  x = 1;
  B[bpos] |= (1 << apos);
  if (x < 0) break;
}

（我认为起始值7是有符号类型必须具有的最小宽度）。

于 2011-01-27T17:35:56.313 回答
0

为什么这会出现问题？类型的大小在编译时是固定的，因此确定类型的运行时大小的问题归结为确定类型的编译时大小的问题。对于任何给定的目标平台，诸如声明之类的声明off_t offset将被编译为使用某个固定大小，然后在目标平台上运行生成的可执行文件时将始终使用该大小。

ETA：您可以type通过sizeof(type). 然后，您可以与常见的整数大小进行比较并使用相应的MAX/MIN预处理器定义。您可能会发现使用起来更简单：

uintmax_t bitWidth = sizeof(type) * CHAR_BIT;
intmax_t big2 = 2;  /* so we do math using this integer size */
intmax_t sizeMax = big2^bitWidth - 1;
intmax_t sizeMin = -(big2^bitWidth - 1);

仅仅因为一个值可以由底层的“物理”类型表示并不意味着该值对于“逻辑”类型的值是有效的。我想没有提供最大和最小常量的原因是这些是“半透明”类型，其使用仅限于特定域。在需要不透明度的情况下，您通常会找到获取所需信息的方法，例如可以用来计算 SUSv2 在其描述off_t中提到的.<unistd.h>

于 2011-04-20T22:27:23.177 回答
0

对于没有关联无符号类型名称的不透明有符号类型，这是无法以可移植方式解决的，因为任何检测是否存在填充位的尝试都会产生实现定义的行为或未定义的行为。您可以通过测试（无需额外知识）推断出的最好的事情是至少有K个填充位。

顺便说一句，这并不能真正回答问题，但在实践中仍然有用：如果假设有符号整数类型T没有填充位，则可以使用以下宏：

#define MAXVAL(T) (((((T) 1 << (sizeof(T) * CHAR_BIT - 2)) - 1) * 2) + 1)

这可能是一个人能做的最好的事情。它很简单，不需要对 C 实现做任何其他假设。

于 2018-07-23T13:51:18.200 回答
0

也许我没有得到正确的问题，但由于 C 为您提供了 3 种可能的有符号整数表示（http://port70.net/~nsz/c/c11/n1570.html#6.2.6.2）：

  • 符号和大小
  • 一个的补码
  • 二进制补码

并且其中任何一个中的最大值应该是2^(N-1)-1，您应该能够通过获取相应无符号的最大值来获得它， ->>1移动它并将结果转换为正确的类型（它应该适合）。

如果陷阱表示妨碍了我，我不知道如何获得相应的最小值，但如果不是，最小值应该是(Tp)((Tp)-1|(Tp)TP_MAX(Tp))（所有位都设置）(Tp)~TP_MAX(Tp)并且应该很容易找出。

例子：

#include <limits.h>
#define UNSIGNED(Tp,Val) \
    _Generic((Tp)0, \
            _Bool: (_Bool)(Val), \
            char: (unsigned char)(Val), \
            signed char: (unsigned char)(Val), \
            unsigned char: (unsigned char)(Val), \
            short: (unsigned short)(Val), \
            unsigned short: (unsigned short)(Val), \
            int: (unsigned int)(Val), \
            unsigned int: (unsigned int)(Val), \
            long: (unsigned long)(Val), \
            unsigned long: (unsigned long)(Val), \
            long long: (unsigned long long)(Val), \
            unsigned long long: (unsigned long long)(Val) \
            )
#define MIN2__(X,Y) ((X)<(Y)?(X):(Y))
#define UMAX__(Tp) ((Tp)(~((Tp)0)))
#define SMAX__(Tp) ((Tp)( UNSIGNED(Tp,~UNSIGNED(Tp,0))>>1 ))
#define SMIN__(Tp) ((Tp)MIN2__( \
                    (Tp)(((Tp)-1)|SMAX__(Tp)), \
                    (Tp)(~SMAX__(Tp)) ))
#define TP_MAX(Tp) ((((Tp)-1)>0)?UMAX__(Tp):SMAX__(Tp))
#define TP_MIN(Tp) ((((Tp)-1)>0)?((Tp)0): SMIN__(Tp))
int main()
{
#define STC_ASSERT(X) _Static_assert(X,"")
    STC_ASSERT(TP_MAX(int)==INT_MAX);
    STC_ASSERT(TP_MAX(unsigned int)==UINT_MAX);
    STC_ASSERT(TP_MAX(long)==LONG_MAX);
    STC_ASSERT(TP_MAX(unsigned long)==ULONG_MAX);
    STC_ASSERT(TP_MAX(long long)==LLONG_MAX);
    STC_ASSERT(TP_MAX(unsigned long long)==ULLONG_MAX);

    /*STC_ASSERT(TP_MIN(unsigned short)==USHRT_MIN);*/
    STC_ASSERT(TP_MIN(int)==INT_MIN);
    /*STC_ASSERT(TP_MIN(unsigned int)==UINT_MIN);*/
    STC_ASSERT(TP_MIN(long)==LONG_MIN);
    /*STC_ASSERT(TP_MIN(unsigned long)==ULONG_MIN);*/
    STC_ASSERT(TP_MIN(long long)==LLONG_MIN);
    /*STC_ASSERT(TP_MIN(unsigned long long)==ULLONG_MIN);*/

    STC_ASSERT(TP_MAX(char)==CHAR_MAX);
    STC_ASSERT(TP_MAX(signed char)==SCHAR_MAX);
    STC_ASSERT(TP_MAX(short)==SHRT_MAX);
    STC_ASSERT(TP_MAX(unsigned short)==USHRT_MAX);

    STC_ASSERT(TP_MIN(char)==CHAR_MIN);
    STC_ASSERT(TP_MIN(signed char)==SCHAR_MIN);
    STC_ASSERT(TP_MIN(short)==SHRT_MIN);
}
于 2018-11-25T17:31:20.897 回答
0

对于所有真机，（二进制补码且无填充）：

type tmp = ((type)1)<< (CHAR_BIT*sizeof(type)-2);
max = tmp + (tmp-1);

使用 C++，您可以在编译时计算它。

template <class T>
struct signed_max
{
      static const T max_tmp =  T(T(1) << sizeof(T)*CO_CHAR_BIT-2u);    
      static const T value = max_tmp + T(max_tmp -1u);
};
于 2020-09-16T22:36:12.477 回答
-3

在问问题“如何？”之前 ，首先你需要问一个问题“为什么？” . 为什么你真的需要在运行时知道这一点？这与真正的问题有关还是只是一个学术问题？

我真的认为没有必要在编译时确定这一点。如果程序员正在编写程序以满足特定需求，那么他肯定对它将运行的环境有所了解。

于 2011-04-26T12:52:57.293 回答