关于UB(未定义行为)的一个小发现

常规
1

省流 十年OI一场空，一用memset见祖宗

前情提要

很普通的一道 普及+/提高 的题，题面如下：

P10725 [GESP202406 八级] 最远点对

题目描述

小杨有一棵包含 n 个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。

小杨想知道相距最远的一对不同颜色节点的距离是多少。

输入格式

第一行包含一个正整数 n，代表树的节点数。

第二行包含 n 个非负整数 $a_1,a_2,\cdots,a_n$（对于所有的 1\le i\le n，均有 a_i 等于 0 或 $1$），其中如果 a_i=0，则节点 i 的颜色为白色；如果 a_i=1，则节点 i 的颜色为黑色。

之后 (n-1) 行，每行包含两个正整数 x_i,y_i，代表存在一条连接节点 x_i 和 y_i 的边。

保证输入的树中存在不同颜色的点。

输出格式

输出一个整数，代表相距最远的一对不同颜色节点的距离。

输入输出样例 #1

输入 #1

5
0 1 0 1 0
1 2
1 3
3 4
3 5

输出 #1

3

说明/提示

样例解释

相距最远的不同颜色的一对节点为节点 2 和 5。

数据范围

本题采用捆绑测试。

子任务编号 得分 n a_i 特殊条件
1 30 \le 10^5 0\le a_i\le 1 树的形态为一条链
2 30 \le 10^3 0\le a_i\le 1
3 40 \le 10^5 0\le a_i\le 1

对于全部数据，保证有 1\le n\le 10^5，0\le a_i\le 1。

明显可以用树上DP求解，定义状态

dp_{u,0} \Rightarrow u \text{ 的子树中，距离 } u \text{ 最近的白色点的最远距离}
dp_{u,1} \Rightarrow u \text{ 的子树中，距离 } u \text{ 最近的黑色点的最远距离}

得出状态转移方程

(a) 计算当前子树

我们要找不同颜色的最远点对。

  • 如果在 u 当前已知的子树部分中，最远的白点距离是 dp[u][0]，
  • 而在子树 v 中，最远的黑点距离是 dp[v][1]，

则通过边 (u,v) 可以形成一条路径，长度为：

dp_{x,0} + dp_{nxt,1} + 1

（+1 是因为 u 和 v 之间有一条边）

同理，也可能是：

dp_{x,1} + dp_{nxt,0} + 1

更新答案

ans=max(max(dp[x][0]+dp[nxt][1],dp[x][1]+dp[nxt][0])+1,ans);

记住这句话，后面要考

(b) 向上返回

dp_{x,0} = \max(dp_{x,0}, dp_{nxt,0}+1)
dp_{x,1} = \max(dp_{x,1}, dp_{nxt,1}+1)

表示如果 v 的子树中有某个最远的白点或黑点，那么到 u 的距离要加 1。

更新答案

dp[x][0]=max(dp[x][0],dp[nxt][0]+1);
dp[x][1]=max(dp[x][1],dp[nxt][1]+1);

很快写出如下代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
int color[100005];
int dp[100005][2];
vector<int> edge[100005];
void dfs(int x,int fa)
{
	for(int i=0;i< edge[x].size();i++)
	{
		int nxt=edge[x][i];
		if(nxt==fa)	continue;
		dfs(nxt,x);
		ans=max(max(dp[x][0]+dp[nxt][1],dp[x][1]+dp[nxt][0])+1,ans);
		dp[x][0]=max(dp[x][0],dp[nxt][0]+1);
		dp[x][1]=max(dp[x][1],dp[nxt][1]+1);
	}
	return;
}
signed main()
{
	memset(dp,0x80,sizeof dp);
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>color[i];
	for(int i=1;i<=n;i++)	dp[i][color[i]]=0;
	for(int i=1;i< n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

问题浮现

一运行，坏了

PS C:\Users\77570\Documents> g++.exe "C:\Users\77570\Documents\P10725 [GESP202406 八级] 最远点对.cpp" -o "C:\Users\77570\Documents\P10725 [GESP202406 八级] 最远点对.exe" -g3 -std=c++17
PS C:\Users\77570\Documents> C:\Users\77570\Documents\"P10725 [GESP202406 八级] 最远点对.exe"
5
0 1 0 1 0
1 2
1 3
3 4
3 5
72340172838076673
PS C:\Users\77570\Documents>

我去，这是啥

简单观察发现，72340172838076673=0x101010101010101。
凭经验，大抵是溢出了，把0x80换成个0xcf试试看

PS C:\Users\77570\Documents> g++.exe "C:\Users\77570\Documents\P10725 [GESP202406 八级] 最远点对.cpp" -o "C:\Users\77570\Documents\P10725 [GESP202406 八级] 最远点对.exe" -g3 -std=c++17
PS C:\Users\77570\Documents> C:\Users\77570\Documents\"P10725 [GESP202406 八级] 最远点对.exe"
5
0 1 0 1 0
1 2
1 3
3 4
3 5
3
PS C:\Users\77570\Documents>

修好了？

不会吧，0x8080808080808080离LONG_LONG_MIN还远着，仅仅+1 -1的递推爆不了

然后就对着递推式盯了30min 糖逼一个

猛然间发现我的代码里有一句

ans=max(max(dp[x][0]+dp[nxt][1],dp[x][1]+dp[nxt][0])+1,ans);

完辣

0x80+0x80必然爆，而0xcf+0xcf没事。

GPT是这么回答的

:white_check_mark: 是的，0x80 这个例子可以说是一个极其经典、标准教科书级的「补码溢出陷阱」案例。
它几乎把**有符号补码整数的一切“坑点”**都展示得淋漓尽致。

下面我带你逐层解析为什么它这么典型:backhand_index_pointing_down:

:puzzle_piece: 一、为什么说“典型”

我们先看 0x80 填充的结果：

memset(dp, 0x80, sizeof dp);

对一个 64 位的 long long，每个字节都是 0x80：

0x8080808080808080

这在补码中表示：

十进制 = -9187201950435737472 ≈ -9.187×10^18

非常接近 long long 的最小值 −9.223372036854775808×10^18。

这就是陷阱的开端。

:gear: 二、补码的定义复习

对于一个 n 位补码整数：

负数 x = 2^n − |x|

对于 0x8080808080808080：

x = 2^64 - 0x7F7F7F7F7F7F7F80
  = -9187201950435737472

最高位 1 → 表示负数。
这没问题，但是——它离 LLONG_MIN 太近了！

:bomb: 三、陷阱：一加就炸

在 DFS 中出现的操作：

ans = max(ans, dp[x][0] + dp[y][1] + 1);

于是：

(-9.187e18) + (-9.187e18) + 1 = -1.837e19 + 1

数学上，这个结果小于 LLONG_MIN = -9.223e18，
所以它 溢出了 long long 的表示范围。

:warning: 四、C++ 层面：这就是 “有符号溢出 UB”

C++ 标准（[expr.add]/10）明文规定：

如果加法或减法的结果超出目标有符号整数类型能表示的范围，则行为未定义。

也就是说：

  • 编译器不保证结果正确
  • 甚至不保证程序继续正常执行
  • 任何结果（正数、负数、NaN）都可能出现

:nut_and_bolt: 五、CPU 层面：补码模加（真实硬件行为）

虽然语言标准说“UB”，但硬件不会真的炸，它执行模 2⁶⁴ 加法：

0x8080808080808080 + 0x8080808080808080 = 0x0101010101010100
再 +1 → 0x0101010101010101

于是你得到：

72340172838076673 = 0x0101010101010101

也就是负负得正，结果反而成了小正数。

这就是最危险的地方：

程序没崩，但逻辑已彻底错。

:brain: 六、为什么说它“教科书级”

这个例子之所以经典，是因为它完美击中三个补码陷阱点：

陷阱 0x80 是否命中 说明
① 字节填充与整数解释不同 :white_check_mark: memset 按字节填，不是按整数
② 有符号溢出是 UB :white_check_mark: a + a 超出 long long 范围
③ 补码模加回绕导致逻辑错误 :white_check_mark: 溢出后翻回正区间，结果看似“正常”

简直是“补码未定义行为三连击”。

:microscope: 七、这类陷阱的泛化版本

0x80 在不同位宽上都会“炸”：

位宽 填充字节 实际值（补码解释） 加自己后
8 位 0x80 −128 溢出为 0
16 位 0x8080 −32640 溢出为 0x0100
32 位 0x80808080 −2139062144 溢出为 0x01010100
64 位 0x8080808080808080 −9187201950435737472 溢出为 0x0101010101010100

无论在哪种宽度上，“一加自己就翻正”。

这就是为什么 0x80 是个**“万能溢出示例”**。

:white_check_mark: 八、对比“安全”的字节填充

填充值 补码解释 加自己结果 UB？ 备注
0x00 0 0 :cross_mark: 安全但无意义
0xFF −1 −2 :cross_mark: 补码闭合，安全
0x80 −9.18e18 溢出 :white_check_mark: :fire:典型陷阱
0x88 −8.60e18 溢出 :white_check_mark: “神秘 0x1111…” 案例
0xCF −3.50e18 不溢出 :warning: 仍依赖补码机器

:light_bulb: 九、结论

0x80 是一个标准补码溢出陷阱案例。
它体现了：
:one: memset 字节填充与整数初始化的危险组合；
:two: 有符号溢出的未定义行为；
:three: 模 2⁶⁴ 加法“负负得正”的错觉；
:four: 补码世界中“静默错误”的致命性。

几乎所有编译器和 CPU 都能在这个例子上验证补码模型的行为，
因此它在教学、调试和标准分析中经常被用作经典演示。

:magnifying_glass_tilted_left: 十、总结成一句话：

memset(..., 0x80, ...) 是补码世界里最漂亮的一颗“定时炸弹”：
**看似只是个负数，实则一加就翻正，且无警告、无崩溃、结果错得离谱。

这样就可以该出正确答案了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
int color[100005];
int dp[100005][2];
vector<int> edge[100005];
void dfs(int x,int fa)
{
	for(int i=0;i< edge[x].size();i++)
	{
		int nxt=edge[x][i];
		if(nxt==fa)	continue;
		dfs(nxt,x);
		ans=max(max(dp[x][0]+dp[nxt][1],dp[x][1]+dp[nxt][0])+1,ans);
		dp[x][0]=max(dp[x][0],dp[nxt][0]+1);
		dp[x][1]=max(dp[x][1],dp[nxt][1]+1);
	}
	return;
}
signed main()
{
	memset(dp,0xff,sizeof dp);
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>color[i];
	for(int i=1;i<=n;i++)	dp[i][color[i]]=0;
	for(int i=1;i< n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

完结撒花！

1 个赞