64位整数问题

题目描述

输入正整数n，统计它的正因子个数，n<= 10^(12),例如n=30时，输出应该为8。

源码

#include <stdio.h>
#include <math.h>

int main () {
  int64_t a;
  int count = 0;
  printf("请输入一个正整数：");
  scanf("%lld", &a);
  if (a <= 0 || a > pow(10, 12)) {
      printf("请输入一个正整数，小于10^(12)");
  } else {
      for (int i = 1; i <= sqrt(a); i++) {
          if ((a % i) == 0) {
              count += 2;
          }
      }
      printf("%d\n", count);
  }
  return 0;
}

剖析

这个题逻辑并不复杂，核心在于分析整型字节数。

1.整型长度

咱们先复习几个概念知识。

• 机器字长

机器字长指的是CPU一次性能处理的二进制位（Bit），如x86-32位、x86-64位架构。机器字长代表了硬件处理速度，CPU处理字长越大，则效率越高，对寄存器、总线宽度要求也就越高。同时，机器字长也是寄存器长度，所以指针字节数跟硬件配置相关。因为指针存储的就是地址。64位CPU，指针大小为8字节。CPU对应的指令字长不一定与机器字长相同，比如为了兼容，64位机器字长也可以支持32位指令字长。

• 32位、64位操作系统

操作系统是运行在硬件上层的第一层软件，而操作系统字长则等于指令字长， 小于等于 机器字长。比如你买了64位架构的电脑，装了个32位的操作系统。

所以究竟是机器字长决定整型数字长还是操作系统字长？都不是。

• 编译器决定数据字长

我使用的gcc编译器。整型数据长度实际是由编译器根据自身硬件长度决定的。

Each compiler is free to choose appropriate sizes for its own hardware, subject only to the restriction that shorts and ints are at least 16bits, longs are at least 32bits, and short is no longer than int, which is no longer than long.

以GCC为例，在32位、64位操作系统中，short 是 2个字节，int 是4个字节，32位系统中long 4个字节、long long 8个字节，64位系统中long 与 long long 都是 8个字节。

题目中输入数小于等于10¹²，大约是2¹⁴，已经超过了int表示的范围，略宽于-2 * 10⁹ ~ 2 * 10⁹ -1.所以采用了64位整型数据类型，等同于使用 long long，范围大约略宽于 -8 * 10¹⁸ ~ 8 * 10¹⁸ -1。

2.循环次数

如果i是n的因子，那么n/i也是n的因子，所以只需要遍历到n的算术平方根即可。

3.输入校验

题目对输入数据有大小显示，所以做下必要的校验。

参考

int类型究竟占几个字节
CPU位数、操作系统位数、计算机字长、C/C++基本数据类型长度