今天在CSDN上看到一个有意思的小题目,题目如下:

int main(){
    if(/*在此填入一个语句*/) printf("Hello");
    else printf(" World!");
}

要求填入一个语句,能够使上面的程序顺利打印出helloworld。

Tagged with:
 

Linux内核信号处理机制介绍

On October 9, 2010, in linux, linux内核, by sponge

本文简单介绍下Linux信号处理机制,为介绍二进制翻译下信号处理机制做一个铺垫。

首先,先说一下什么是信号。信号本质上是在软件层次上对中断机制的一种模拟,其主要有以下几种来源:

  1. 程序错误:除零,非法内存访问…
  2. 外部信号:终端Ctrl-C产生SGINT信号,定时器到期产生SIGALRM…
  3. 显式请求:kill函数允许进程发送任何信号给其他进程或进程组。

在Linux下,可以通过以下命令查看系统所有的信号:

kill -l

可以通过类似下面的命令显式的给一个进程发送一个信号:

kill -2 pid

上面的命令将2号信号发送给进程id为pid的进程。不存在编号为0的信号。

目前Linux支持64种信号。信号分为非实时信号(不可靠信号)和实时信号(可靠信号)两种类型,对应于 Linux 的信号值为 1-31 和 34-64。信号是异步的,一个进程不必通过任何操作来等待信号的到达,事实上,进程也不知道信号到底什么时候到达。本文着重于Linux的信号处理机制,对信号更多的介绍可以参考这里

本来不想往blog上面贴一大堆代码的,不过好不容易写出来了,贴出来给大家做个参考把!

程序输入一连串的整数序列,会根据这个整数序列构建一个平衡二叉树。

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>
//节点数据结构
struct node{
int val;//值
int bf;//平衡因子
struct node* left;
struct node* right;
};

Linux下常用的函数调用栈规范

On October 6, 2010, in linux, linux系统, by sponge

我们都应该知道,高级语言的函数调用过程中,有“栈”这么一个概念,被调用函数的局部变量是存放在栈中的,函数调用的参数也是通过栈传递的。那么,调用函数是怎么把各种数据压入栈中,被调用函数又是怎么对栈进行操作以获取必要的数据呢?函数调用发生完毕之后,谁又负责清理这个栈?这就用到了函数调用栈规范!

函数调用栈规范是指编译器的一中“约定”,他规定了调用者如何传递参数,被调用者如何获取参数,调用完成后怎么清理栈,怎么传递返回值等。编译器在编译程序的时候遵循这种规范,从而使程序正确的执行。对于不同的编译器,不同的高级语言,这种规范是不尽相同的。

在X86平台下的Linux内核中,常用的函数调用规范有:C,FastCall,Pascal等,下面简单介绍下这几种规范:

上篇日志中提出了一个EMC某年的笔试题目,题目如下:

题目:

函数声明如下:

int func(int i, int N);

其中,i<=N, 功能输出i递增到N再递减到i的整数,每行输出一个数。比如func(1, 5)的输出是:

1
2
3
4
5
4
3
2
1

要求:

  1. 函数中只能有一个语句,即1个分号。
  2. 不能使用do while until goto for if关键字,不能使用?:和逗号操作符。
  3. 唯一能使用的库函数为printf。

&&与||的妙用

On September 30, 2010, in C语言, 笔试面试, 语言学习, by sponge

我们都知道,&&是逻辑与, ||是逻辑或。对于这两个运算符,有下面的性质:

1 && 1 = 1; 1 && 0 = 0; 0 && 1 = 0; 0 && 0 = 0;
1 || 1 = 1; 1 || 0 = 1; 0 || 1 = 1; 0 || 0 = 0;

出了这些基本的性质之外,额外需要注意的是,在C语言中,这两个运算符有如下的性质:

  1. && 的 优先级高于 ||
  2. 让我们看如下代码:

Tagged with:
 

优化算法复杂度的技巧-位操作

On September 29, 2010, in 笔试面试, 算法, by sponge

算法是很巧妙的东西,很多时候你以为你写了一个时间复杂度和空间复杂度最低的算法,但实际上还有更好的方法,让我们来看两个通过位操作优化的小算法。

第一题:给两个变量a和b,如何不使用第三个变量,而交换a和b的值?
第二题:假设给一个长度为2n+1的数组,数组中有n个数是成对出现的,求只出现一次的数的值。要求尽量降低时间和空间复杂度。

第一个题目相对比较简单,第二个题目我觉得大多数人也能给出比较好的答案,大家不妨先思考下再看下面的答案。

Tagged with:
 

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。

现在给出旋转后的数组和一个数,旋转了多少位不知道,要求给出一个算法,算出给出的数在该数组中的下标,如果没有找到这个数,则返回-1。要求查找次数不能超过n。

这个题要想尽量减少是件复杂度,我觉得使用二分查找最好,只是需要稍微变化下,下面给出C语言描述的程序:

Tagged with:
 

fork

是linux下的一个系统调用,它的作用是产生一个子进程,子进程是当前进程的一个副本,它跟父进程有一样的虚存内容,但也有一些不同点,读者可以自己参考这里
但是,值得注意的是,父进程调用fork()后,fork()返回的是生成的子进程(如果能顺利生成的话)的ID。子进程执行的起点也是代码中fork的位置,不同的是子进程fork()返回的是0。如下代码:

int i;
i = fork();
printf("%d\n",i);

这段代码中,父进程打印出来的值是“子进程id”,而子进程打印出来的是0。

www.spongeliu.com
好了,废话介绍完了,让我们切入正题,看两个比较有意思的C语言题目。
www.spongeliu.com

Tagged with:
 

Linux设备驱动程序简介

On September 28, 2010, in linux, linux内核, by sponge

因为最近项目关系,需要动态二进制翻译一个驱动,所以看了下驱动相关知识,并在这里做一个简单普及性的介绍。
.
首先,我们都知道,Linux分为用户态和内核态,一般应用程序是在用户态执行,他们通过一系列的系统调用同内核态进行交互。那么驱动程序扮演一个什么样的角色呢?
.
驱动程序是内核与硬件的接口,他把系统调用映射到具体设备对于实际硬件的特定操作上,关系如下图所示:

.

Page 3 of 41234