我以为自己发现了 clang 的一个 bug……

摘要:完成体系结构课程作业时遇到 gcc 和 clang 的行为不一样。确切地说是 clang -O1 及以上会得到意外的结果。以为自己搞了个大新闻,结果发现是自己写了 ub(未定义行为,undefined behavior)。

代码如下。

#include <stdio.h>
#include <limits.h>
int test(int x, int n)
{
  int y = (1 << (n - 1)) - 1;
  int le = (x <= y);
  printf("%d, %d, %d\n", x, y, le);
  return 0;
}

int main(){
  int n = sizeof(int) * 8;
  test(INT_MIN, n);
  return 0;
}

gcc 版本:gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
输出的结果是:

$ gcc bar.c -O1 -o g && ./g
-2147483648, 2147483647, 1

clang 版本:Ubuntu clang version 3.4-1ubuntu3 (tags/RELEASE_34/final) (based on LLVM 3.4)
输出的结果是:

$ clang bar.c -O1 -o c && ./c
-2147483648, 2147483647, 0

 

好奇怪啊,明明一个正数、一个负数,怎么 clang -O1 就负数更大了呢???

是不是 clang 编译优化的 bug?

——我也以为自己搞了个大新闻。仔细研究一番便发现,这里并不能怪编译器:1 << 31 已经发生了溢出;即使得到了负值 INT_MIN,在其上再减去 1,再次发生溢出。对于有符号整数运算溢出,尽管很常见的做法是截断取模,但实际上标准并没有作出规定。因此,从这一行起,编译器做什么都是符合标准的( ̄(工) ̄)

ub 很可能直接被编译器优化掉[1]。此处就是这样。可以从汇编码看出,开启编译优化时,clang 把 le 参数直接优化掉了,大意如此:

printf("%d, %d, %d\n", x, y, le); //clang -O0
printf("%d, %d, %d\n", x, y, 0);  //clang -O1

完。

如何进行算术表达式的求值

问题:对一个形如“(2!)^(cos(0)+(-2))”的算术表达式求值。

最近《数据结构》课程讲到堆栈的应用,碰到了这个经典的问题:数学表达式的求值。

众所周知,双目运算符有中缀式(自然形式)、前缀式(波兰表达式)、后缀式(逆波兰表达式)三种表示方法,其中后两种易于求值(只需顺序扫描一遍即可)。一种典型的想法是,先把中缀式转换为后缀式(如果利用堆栈,大致是线性时间、线性空间),然后对后缀式求值(线性时间)。

但是这种方法看起来只对二元运算符有效。如果出现了一元运算符,比如 “-1”,这里这个表示一元“取反”运算的负号,需要被转化成 “0-1”,变成二元“减法”运算的减号,方可用前缀式或后缀式求值。除了出现在运算数前面,一元运算符还可以出现在运算数后面,比如阶乘。更甚者,一元运算符可以以“函数”的形式出现,引入更多的括号,比如下式:

(2!)^(cos(0)+(-2))

实际上我们可以认为 f(x),fx,xf 是一元运算符的三种形式。

问题:对一个含有一元运算符、二元运算符、括号的自然形式的算术表达式求值。其中一元运算符的形式包括 “sin(233)”、“-233”、“233!”。

本文将给出一种处理以上问题的有效算法。这一算法在表达式的自身形式上进行迭代,近似具有平方(表达式长度 x 运算符个数)的时间复杂度。可改用栈结构避免重复扫描查找括号,可降低时间复杂度,但将需要线性的额外空间。

1 顺序扫描,查找最内层的一对括号(最靠右的“(”和相应的“)”)

2 查找括号内是否有运算符
    2.1 如果有,对括号内的部分进行求值(子问题)
    2.2 如果没有,检查括号左侧是否有函数名
        2.2.1 如果有,求值
        2.2.2 如果没有,去掉括号

3 重复以上步骤,直到找不到任何括号

其中调用了一个子问题:对不含括号的表达式求值。这时候只有 fx 和 xf 两种形式的一元运算符,且识别起来相当容易:与其他运算符相邻的运算符就是一元运算符。可以先将所有一元运算符求值,然后按正常二元运算符表达式的方法求值。

以下是该算法作用于上例的过程。为避免二义性,以 @ 表示“表示数值的负号”,与运算符“-”区分。

(2!)^(cos(0)+(-2))
(2!)^(cos(0)+(@2))
(2!)^(cos(0)+@2)
(2!)^((1)+@2)
(2!)^(1+@2)
最内层 (1+@2)
最内层 @1
(2!)^(@1)
(2!)^@1
最内层 (2!)
最内层 2
(2)^@1
2^@1
最内层 (2^@1)
最内层 0.5
0.5

以下链接是我(/*于一年前←_←*/)按照该算法写的 C 语言程序,它可以处理前置的一元运算符“-”(取负)、后置的一元运算符“!”(阶乘),可以处理十二种函数 {“cos”,”sin”,”tg”,”ctg”,”abs”,”sign”,”sqrt”,”ln”,”sinh”,”cosh”,”tanh”,”coth”},可以处理五种二元运算符 {‘+’, ‘-‘, ‘*’, ‘/’, ‘^’},可以正确处理括号,同时还实现了一部分大数计算。

https://github.com/lizy14/C-assignments/blob/master/expressionCALC.cpp

(完)

C/C++ 判断整数相加是否溢出

算术方法,或者内联汇编判断溢出标志位

方法1:算术方法,根据运算结果判断。
这种判断方法非常直接。

int isAddOverflow1(int x, int y)
{
    int z = x + y;
    if(x > 0 && y > 0 && z < 0)
        return 1;  
    if(x < 0 && y <  0 && z > 0)
        return 1;
    return 0;
}

方法2:从 CPU 读取溢出标志位。
8086 的控制寄存器里的标志寄存器 FLAG 里有个 OF 溢出标志位,如果上一次运算发生溢出,该位会被置 1。使用 jo 指令可依该标志位跳转。
采用内联汇编。以下代码是 VC 的写法。gcc 相应的关键字是 __ASM__。

//compile with MSVC, run on 8086
int isAddOverflow2(int a, int b) {
    __asm {
        mov eax,a
        add eax,b
        jo  overflowed
        xor eax,eax
        jmp no_overflowed
overflowed:
        mov eax,1
no_overflowed:
    }
}

可采用以下程序进行测试:

#include 
int isAddOverflow1(int x, int y);
int isAddOverflow2(int a, int b);
int main() {
    int a,b;
    int samplesA[]={-23333, -1, 0, 1, 2, 2333333};
    int nSamplesA = sizeof(samplesA)/sizeof(int);
    int samplesB[]={233333, 2147483647, -2147483647, -2147483648};
    int nSamplesB = sizeof(samplesB)/sizeof(int);
    for(int iA=0; iA

如有其他方法,欢迎评论补充。本文整理自网上资料。(完)

寻找下一个浮点数

求比给定浮点数大的最小浮点数

这是清华大学软件学院雍俊海老师《软件工程(2)》课程的一道思考练习题。

实现实数类CP_Real的“++”和“–”运算符重载。要求“++”是将当前的浮点数变为下一个浮点数,即变为比当前浮点数大的最小浮点数。要求“–”是将当前的浮点数变为上一个浮点数,即变为比当前浮点数小的最大浮点数。

为此需要研究浮点数在计算机中实际的二进制表示……

我们知道只需要给尾数 +1 就可以了。

我们需要让编译器把浮点数当成整数,以让 CPU 进行整数的 +1 运算。问题是,我们必须防止编译器“自作聪明”地做强制转换。为此,我们先取地址,得到一个浮点数指针,然后强制转换为整型指针,此时内存中的数据并没有变化;送入 CPU 做完整数加法之后,再反过来做一遍……这样就骗过了编译器。

(我估计这件事用汇编语言来写……会更简单吧)

好在,从资料上学习了一种新的类型转换的运算符:( type & )。这就是我们要的,和强制转换并不一样,这个只是把内存中的数据重新解读,而没有做任何实质转换。

以下两种形式的作用相同。

*((int*)&a)
(int&)a

顺便指出,需要注意的是以下三种写法的意义互不相同。

(int)a
(int&)a
(int)&a

运算符重载的操作就不再赘述。下面贴测试代码。

//只对 IEEE 754,int 和 float 等长负责,可能有 bug
#include 
float increment(float a){
	int b=(((int&)a)+(a>=0?1:-1));
	return (float&)(b);
}

int main(){
	float samples[]={0, 0.1, 1e-9, 2.33, 1e20, -0.1, -1e-9, -2.33, -1e20};
	int n=sizeof(samples)/sizeof(float);
	for(int i=0; i

以上代码在 GCC 4.8.1 编译运行的结果是:

0.0000000000000000000000000000000000000000000000000000000000000000000000
0.0000000000000000000000000000000000000000000014012984643248171000000000

0.1000000014901161200000000000000000000000000000000000000000000000000000
0.1000000089406967200000000000000000000000000000000000000000000000000000

0.0000000009999999717180685400000000000000000000000000000000000000000000
0.0000000010000000827403710000000000000000000000000000000000000000000000

2.3299999237060547000000000000000000000000000000000000000000000000000000
2.3300001621246338000000000000000000000000000000000000000000000000000000

100000002004087730000.0000000000000000000000000000000000000000000000000000000000000000000000
100000010800180760000.0000000000000000000000000000000000000000000000000000000000000000000000

-0.1000000014901161200000000000000000000000000000000000000000000000000000
-0.0999999940395355220000000000000000000000000000000000000000000000000000

-0.0000000009999999717180685400000000000000000000000000000000000000000000
-0.0000000009999998606957660700000000000000000000000000000000000000000000

-2.3299999237060547000000000000000000000000000000000000000000000000000000
-2.3299996852874756000000000000000000000000000000000000000000000000000000

-100000002004087730000.0000000000000000000000000000000000000000000000000000000000000000000000
-99999993207994712000.0000000000000000000000000000000000000000000000000000000000000000000000

(完)

投针法生成正态分布随机数

用投针法,将“均匀分布随机数”转化为“正态分布随机数”,附 C 语言源代码。

恩,主流程序设计语言都提供生成(伪)随机数的函数,比如 C 的 rand():

The rand() function returns a pseudo-random integer in the range 0 to RAND_MAX inclusive (i.e., the mathematical range [0, RAND_MAX]).

江湖传言,该函数给出的随机数服从均匀分布。果真如此吗……?恩,试一下不就知道了嘛。来十万个。

好极了。不过区间 [0, RAND_MAX] 并不实用。我们用以下函数把它拓展为任意的 [min, max]:

double randUniform(double min, double max){
	return (rand()/(RAND_MAX + 1.0)*((max)-(min))+(min));
}

下面我们将利用这个函数生成服从正态分布的随机数。我们打算用投针法。

原理是,先画出所要正态分布的概率密度曲线,然后拿一个矩形框起来,然后在这个矩形内随机取点(投针)。舍弃那些落在曲线上方的点。剩下的点的 x 坐标是我们要的。

从原理可以看出,本方法可以拓展到任意已知概率密度函数的分布。缺陷是,只能在有限区间内生成随机数,且并不能保证在有限步骤内结束

效果是极好的。比如我们生成 100000 个,保存到文件中,用 Mathematica 画出来,与标准正态曲线放在一起比较:

以下是 C 语言的源代码。

#include 
#include 
#include 
#include 

#define PI 4.0*atan(1.0)
#define E exp(1.0)

//uniform distribution in range [min, max]
double randUniform(double min, double max){
	return (rand()/(RAND_MAX + 1.0)*((max)-(min))+(min));
}
//probability density function of normal distribution
double pdfNormal(double x, double mu, double sigma){
	return 1/(pow(E,pow(-mu+x,2)/(2.0*pow(sigma,2)))*sqrt(2*PI)*sigma);
}
//normal distribution (mu, sigma), in range [-k*sigma, k*sigma]
double randNormal(double mu, double sigma, double k){
	double x, y, ymax=pdfNormal(mu,mu,sigma), xmax=k*sigma;
	while(233){
		x = randUniform(-xmax, xmax);
		y = randUniform(0,ymax);
		if(y
	

循环赛最短赛程问题

设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。这也许是程序设计课程的经典题目了。不同的是,本文希望探讨人数不是 2 的整数次幂的情形。

要求是,设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。

一种易于写成递归算法的想法是这样。

【方案一】

  • 假如我们已经安排好了 n 个人的单循环赛程表,用时 d 天。
  • 那么,对于 2n 人,我们可以这样安排:
    • 将这 2n 人分成两组,每组 n 人。为便于叙述,记为 甲组 和 乙组。
    • 在前 d 天,让每组的 n 个人分别进行单循环(这将是递归调用);
    • 之后花 n 天,完成所有“一个选手来自甲组,一个选手来自乙组”的比赛。
      • 比如说,这 n 天中第 1 天,甲组1号 vs 乙组1号,甲组2号 vs 乙组2号,直到甲组n号 vs 乙组n号;
      • 第 2 天,把每个乙组选手的编号加1,安排甲组1号 vs 乙组2号,甲组2号 vs 乙组3号,直到甲组(n-1)号 vs 乙组n号,甲组n号 vs 乙组1号;
      • 这样下去第 n 天,安排 甲组1号 vs 乙组n号,甲组2号 vs 乙组1号,直到甲组(n-1)号 vs 乙组(n-2)号,甲组n号 vs 乙组(n-1)号。

可以验证,以上的方案安排比赛,可以做到不重不漏。当 n = 2 时显然有 d = 1,继而可以用数学归纳法证明,

当比赛人数 n 是 2 的幂次(比如 4, 8, 256, 2048, 65536)时,以上方法可以让比赛用时 (n-1) 天结束。

下面来证明该方案是用时最短的方案——根据单循环“每两个选手都比赛一次”的要求,n 人的单循环要比赛 n(n-1)/2 场,而根据“每位选手每天最多比赛 1 场”的要求, (n-1) 天最多只能进行 n(n-1)/2 场比赛。所以赛程不可能比 (n-1) 天更短了。

分治递归,该方案容易编程实现。附 C 语言的代码。

以上方案有个明显的缺陷——只能处理比赛人数 n 是 2 的幂次的情况。如果比赛人数是 33,如果还想用这个方案的话,我们将只能“虚拟”出第 34 到 64 号选手来,然后按 64 个选手来安排。赛程将是 63 天。当然其中有大量的比赛是实际不存在的。有虚拟选手参加的比赛直接从赛程表上抹掉就可以了,不必担心真选手或者裁判员被虚拟选手“放鸽子”自不必担心。我心疼的是,轮空太多了,赛程中的时间将被白白浪费掉。

下面我们希望解决的问题是,对于比赛人数是 33 人这种情况,我们是否可以设计出更短的赛程?

对于人数是奇数的情况,我们首先可以给出日程长度的下限:n,因为要比赛 n(n-1)/2 场,而每天最多只能进行 (n-1)/2 场比赛。对于人数是偶数的情况,同样方法给出的下限是 (n-1)。

下面是资料给出的,人数是偶数时,(n-1) 天搞定的排法:

【方案二】

来源:http://www.docin.com/p-430759465.html

容易验证该方案满足要求。而对于人数是奇数的情况,我们可以虚拟出 1 个选手,应用以上方案,就可以得到一个 n 天的赛程了。

至此我们构造性地证明了以下定理:

若选手数是偶数,单循环赛轮数的最小值是 (n-1) ;若是奇数,最小值是 n 。

(完)

C:可重复执行的命令行程序框架

一个简单的C语言的命令行程序框架,使程序在执行完毕后不退出,等待用户的新一次输入。

程序开始,用户输入,程序输出,return 0,结束。用户若想尝试另一个输入,就不得不重新开始程序。在 Windows,这就将是一次并不必要的双击。

如何省去重新开始,让程序执行完不退出,等待用户的另一次输入?修改源代码,将主要部分放入循环之中?本文给出的就是这样一个框架。

//可重复执行的命令行程序框架
//By Li Zhaoyang

//include
#include 
    
#define MAX_INPUT_LENGTH 65536

int main(){
    puts("欢迎使用ASCII编码查看器。");
    puts("请输入一个整数。输入exit退出程序。");
    while (233)    {
        putchar('\n');
        int n;
        //输入 
        {
            char buffer[MAX_INPUT_LENGTH];
            printf(">>");
            gets(buffer);
            if(!strcmp(buffer, "exit")) return 0;
            //执行scanf并进行异常输入检查
            if((sscanf(buffer, "%d", &n)!= 1)||
                ((n<0)||(n>255))){
                puts("输入不合法");
                continue;
            }
        }
        //主要代码开始
        printf("'%c', %d\n", n, n);
        //主要代码结束 
    }
    return 0;
} 

效果是这样:

E:\_K\p\C>a.exe
欢迎使用ASCII编码查看器。
请输入一个整数。输入exit退出程序。

>>65
'A', 65

>>-10
输入不合法

>>e
输入不合法

>>exit

E:\_K\p\C>

(完)

C语言新手笔记

新手上路,难免遇到各种各样的问题。本文所收录,就是我遇到的,容易忽视的一些问题。

新手上路,难免遇到各种各样的问题。本文所收录,就是我遇到的,容易忽视的一些问题。

1. 常数不可随便写。

int a=14; 
int b=014; //前导零,是八进制的14
float a=3/2;   //得到1
float b=3/2.0; //得到1.5

2. 不要随便移项……

unsigned int x=4;
if (x > 5)
    puts("x>5");
if (x - 5 > 0)
    puts("x-5>0");
//结果将是,输出 "x-5>0"

注意到 x 的类型是 unsigned,(x-5) 的值还是正数。

3. 多一个分号?

int i, sum;
for(i=0; i<=10; i++);
{
    sum += i;
}
printf("%d", sum);
//输出并不是设想中的55,而是11。

你发现了吗,for 一行后面多写了一个分号。有的编译器会对类似情况给出 warning 曰“空的受控语句”,有的则不会,火眼金睛才能发现问题所在。

4. 搞不懂的自增

int a=2;
a/=a++;
//问此时 a 的值

这绝不是 a++ 和 ++a 的区别那么简单。事实上不同编译器会给出不同结果:gcc 3.4 给出 a==1,Turbo C 3.0 和 VC++ 11.0 则给出 a==2。从汇编码中能看出些端倪,但更深入的研究就需要对编译器的理解了。

这个故事告诉我们,不要随意使用自增(自减)运算符,特别是当被执行自增(自减)的变量在表达式中多次出现的时候。

5. 更多编译器相关的代码

int a=0;
printf("%d %d %d", a++, a++, a++);

新手跨语言:C/VB:VB6写界面,VC11写算法

作为一个新手入门的示例程序,我们用 C 写一个求两数之和(A+B Problem)的函数,然后在 VB 程序中调用它。

作为一个新手入门的示例程序,我们用 C 写一个求两数之和(A+B Problem)的函数,然后在 VB 程序中调用它。

在Visual Studio 2012建立一个Win32项目,名为ProjectName。应用程序类型选择DLL。
然后在ProjectName.cpp中写如下代码。

// ProjectName.cpp : 定义 DLL 应用程序的导出函数。
//

#include "stdafx.h"

#define FUNC(x) extern "C" __declspec(dllexport) x __stdcall 

FUNC(int) SUM_(int x, int y)
{
	return x+y;
}

你可以像写普通的标准C函数一样来写这里的函数,唯一的区别是函数头前面要有一大堆关键字。我在这里使用了宏定义 FUNC(返回值类型) 简化。

extern "C" __declspec(dllexport) int/*你的返回值类型*/ __stdcall SUM_/*你的函数名*/ (int x, int y)/*你的参数列表*/

按F7键,生成ProjectName.dll。

在VB6中,建立一个标准EXE工程,在Form1中写以下代码:

Private Declare Function _
    SUM_ _
    Lib _
    "ProjectName.dll" _
    Alias _
    "_SUM_@8" _
    (ByVal x As Long, ByVal y As Long) _
    As Long

Private Sub Form_Load()
    Dim x As Integer, y As Integer, sum As Integer
    x = InputBox("请输入 x")
    y = InputBox("请输入 y")
    z = SUM_(x, y)
    MsgBox x & " + " & y & " = " & z
End Sub

Lib "ProjectName.dll":指定dll文件。建议在这里使用相对路径,把你的dll和exe放在同一目录下。
Alias "_SUM_@8":需根据C中的函数名手动修改。在__stdcall下,VC编译时会在函数名前面加一个下划线,后面加@和参数的总长度(此处是2个int,即8字节)。
ByVal x As Long:ByVal是不可少的。对应C中4字节的int,VB里是Long。

在“文件”菜单中找“生成”,生成工程1.exe。将工程1.exe和ProjectName.dll放置于同一目录下即可。