当前位置：首页 > 编程日记 > 正文

有符号整型的数据范围为什么负数比正数多一个？

编程日记 2024-09-25 16:00:00

背景

我们先看Leetcode的这道题目：

标题：50. Pow(x, n)
难度：中等
https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

示例 4:

输入: 1.00000, -2147483648
输出: 1.00000

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

思路：

我们可以利用 快速幂法 来解决该问题。假设我们要求a^b，那么b可以拆成二进制表示，例如当b = 5时，5的二进制是0101，5 = 2^3×0 + 2^2×1 + 2^1×0 + 2^0×1，因此，我们将a^5转化为算 a^(2^3×0 + 2^2×1 + 2^1×0 + 2^0×1)，即a^(2^0) × a^(2^2)。

我们先算出所有2的幂，然后在算出所有x的2的幂次方。再把n拆成二进制，把二进制当中对应位置是1的值乘起来，就得到了结果。这套方法称为 快速幂法。

C# 实现

public class Solution
{public double MyPow(double x, int n){int neg = n < 0 ? -1 : 1;int g = Math.Abs(n); //* double[] d = new double[32];d[0] = x;for (int i = 1; i < 32; i++){d[i] = d[i - 1] * d[i - 1];}double result = 1.0d;for (int i = 0; i < 32; i++){int mask = 1 << i;if ((mask & g) != 0){result *= d[i];}}return neg != -1 ? result : 1.0 / result;}
}

上面的代码看起来没有错误，但（*）这条语句溢出了。原因是 n = −2^31 取绝对值之后赋值给变量g的时候，超出了整型的最大值2^31 -1，所以产生了错误。修改为long g = Math.Abs((long)n);提交通过。

执行结果：通过
执行用时：56 ms, 在所有 C# 提交中击败了 51.87% 的用户
内存消耗：15.1 MB, 在所有 C# 提交中击败了 50.00% 的用户

我们这里不免存在一个疑问：有符号整型的数据范围为什么负数比正数多一个？

技术分析

二进制有三种不同的表示形式：原码、反码和补码，计算机内部使用补码来表示。

原码：就是其二进制表示（注意，有一位符号位）。
反码：正数的反码就是原码，负数的反码是符号位不变，其余位取反。
补码：正数的补码就是原码，负数的补码是反码+1。
符号位：最高位为符号位，0表示正数，1表示负数。在位运算中符号位也参与运算。

为了简单起见，我们以byte类型举例。

 0 -> 00 00 00 00
-0 -> 00 00 00 001 -> 00 00 00 01
-1 -> 11 11 11 112 -> 00 00 00 10
-2 -> 11 11 11 103 -> 00 00 00 11
-3 -> 11 11 11 01
...127 -> 01 11 11 11
-127 -> 10 00 00 01

可见，每一个正数都有一个对应的补码表示负数，但是通过上面的分析，我们发现-127~127（包括0也没有重复表示）共255个状态，还有一个状态 10 00 00 00 没有利用，它是多少呢？

发现符号位是1，知道这是补码，是负数
补码减1 得出反码 = 01111111
反码取反得到原码 = 10000000=（128）

所以该数为-128。这就是有符号整型的数据范围负数比正数多一个的原因。

总结

我们从一道Leetcode题目产生溢出的异常谈起，娓娓道来整型的数据范围负数比正数多一个的缘由。只有知道其中的原理，我们写出的代码才会更加健壮和稳定。今天就到这里吧！希望对大家有帮助。See You。

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20292.html

有符号整型的数据范围为什么负数比正数多一个？

背景

技术分析

总结

相关文章：

UI设计培训：UI构思创意技巧和方法

博客园 cnblogs博客添加Google Analytics统计

技术图文：Python 位运算防坑指南

聊聊nginx报错499问题

UI设计需要报培训班学习吗

技术图文：位运算技术在求解算法题中的应用

JavaScript学习系列6 充实文档的内容

mapreduce中设置自定义的输入类,进行文本解析(默认以tab键为分隔符)

如何分辨Web前端培训机构的好坏

mysql dba系统学习（19）配置mysql+lvs+keeplived实现Mysql读操作的负载均衡

技术图文：浅析 C# Dictionary实现原理

思念水饺吃成泡沫水饺（图）思念质量门

jQuery动画的显示与隐藏效果

技术图文：字典技术在求解算法题中的应用

[WCF REST] 解决资源并发修改的一个有效的手段：条件更新（Conditional Update）

Netty 之 Zero-copy 的实现（下）

Java中final关键字如何使用?

技术图文：双指针在求解算法题中的应用

【CSON原创】HTML5游戏框架cnGameJS开发实录（外部输入模块篇）

中国科协（深圳）海外人才离岸创新创业基地源创力中心开业，主打国际创业服务...

找java培训机构如何挑选

技术图文：集合技术在求解算法题中的应用

sql server 2008数据导入Oracle方法

nginx+tomcat配置负载均衡集群

参加UI设计培训要学多久

技术图文：C# 语言中的扩展方法

如何在ToolBar中显示文字和图标,自定义图标大小,并和MenuItem关联

C#程序调用cmd执行命令

Java虚拟机的内存空间有几种

技术图文：排序技术在求解算法题中的应用