C 求最大二进制补码整数

Question

我的任务是找到最大的二进制补码整数或 TMax。我完全不知道该怎么做。我知道正确的值是 0x7fffffff，即 2147483647，但我不知道如何得到这个结果。这是 32 位整数的最大数量。我不能使用函数或条件，最多只能使用 4 个操作。谁能帮我解释一下？我知道找到某个位计数的最大数的方法是 2^(bits - 1) - 1，所以 2^(31) - 1 = 2147483647

Answer 1

假设您知道您的机器使用二进制补码表示，这就是您以符合标准的方式这样做的方式：

unsigned int x = ~0u;
x >>= 1;
printf("max int = %d\n", (int)x);

通过使用 unsigned int，您可以防止任何由右移负值引起的实现定义的行为。

Answer 2

find maximum two's complement integer

int TMax = -1u >> 1 或 -1u/2 足以在 INT_MAX == UINT_MAX/2 找到最大值 int,

这 "works" 即使 int 被编码为 2 的补码或现在罕见的 1 的补码或符号大小。

更好用

#include <limits.h>
int TMax = INT_MAX;

其他技巧可能涉及 未定义的、实现定义的、未指定的行为，最好在 C 中避免这些行为。

Answer 3

在两种情况下，您可能会寻找最大正数，给定整数数据类型或给定位数。同样是两种解决方案。

填充并右移

使用大小与所需二进制补码数据类型的大小完全匹配的整数数据类型，您可以通过

解决问题

(unsigned 'type') ^0)>>1

或等价地，

(unsigned 'type') ^0)/2.

例如在short为16位的机器上，

(unsigned short) ^0   ==>  0xFFFF  (65535)
((unsigned short) ^0 ) >> 1  ==>  0x7FFF  (32767)

在 32 位数据类型上，此方法为我们提供 0x7FFFFFFF (2147483647)。

在 C 中，整数类型只有最小大小，c.f。 int 可以是 16 位、32 位或更大。但是，计算中使用的字长必须与预期目标的字长完全匹配。

另外，注意数据必须是无符号类型。有符号类型的右移通常实现为符号扩展移位（符号位被复制到结果中）。

只设置符号位并减1

第二种技术适用于等于或大于所需二进制补码字长的位数的任何字长，是

(unsigned integer_type) 1<<(n-1)-1

例如，在大于或大于 16 的任何整数字长中，我们可以找到 16 的 TMAX 为

(unsigned integer_type) 1<<15  ==>  binary 1000 0000 0000 0000  (0x8000)
(unsigned integer_type) (1<<15 - 1) == > 0111 1111 1111 1111 (0x7FFF)

这是稳健的，几乎适用于任何提供足够字长的场景。

同样，如果计算中的字长是目标的字长，则计算的数据类型必须是无符号的。对于较大的字号，这不是必需的。

例子

在第一个示例中，我们展示了第二种方法适用于 32 位，使用 long 或 long long 类型。

#include <stdio.h>

int main() {

  printf( "%ld\n", (long) ( ( ((unsigned long) 1)<<31 ) - 1 ) );
  printf( "%lld\n", (long long) ( ( ((unsigned long long) 1)<<31 ) - 1 ) );

}

输出：

2147483647
2147483647

这里我们展示了第一种方法，即从所有位组向右移动，当 int 不正好是 32 位时失败，如前所述，这在 C 中是不能保证的。

#include <stdio.h>

int main() {

  printf( "from long long %lld  (%zu bits)\n", ( (unsigned long long) ~0 )>>1,
      sizeof(unsigned long long)*8 );

  printf( "from long %ld  (%zu bits)\n",  ( (unsigned long) ~0 )>>1,
      sizeof(unsigned long)*8  );

  printf( "from int %d  (%zu bits)\n",  ( (unsigned int) ~0 )>>1,
      sizeof(unsigned int)*8  );

  printf( "from short %d  (%zu bits)\n",  ( (unsigned short) ~0 )>>1,
      sizeof(unsigned short)*8  );
}

输出：

from long long 9223372036854775807  (64 bits)
from long 9223372036854775807  (64 bits)
from int 2147483647  (32 bits)
from short 32767  (16 bits)

再次回想一下，C 语言只保证任何整数数据类型的最小大小。 int 可以是 16 位或 32 位或更大，具体取决于您的平台。

Answer 4

感谢大家的帮助！事实证明我不能使用宏、无符号或长整型。我来到这个解决方案：

~(1 << 31)

这生成了正确的输出，所以我将保留它！

C 求最大二进制补码整数

C find maximum two's complement integer

c

binary

twos-complement