25.5 注意函数设计的多样化和效率

同样,函数设计的实现方法也是具有多样化的,实现的方式也不尽相同。有时可以使用普通函数,有时也可以用宏定义。下面就举一个例子说明这个问题。

【例25.5】编写一个将整型数转换为字符串的程序。

设计函数尽量使用void类型,从而简化程序设计。

为了设计方便,先将整数转换为逆序的字符串,然后再将其反序,转换成正确的字符串。程序中完成将整数转换为逆序的字符串序后,用printf语句将其输出以供验证。


#include <stdio.h>
void itoa
(char *buf
, int num
);          //
转换函数
void reverse
( char buf
, int i
);          //
反序函数
void swap
( char *a
, char *b
);          //
交换函数
int main
()
{
     int num = 0
;                    //
接受键盘输入应初始化为0
     char buf[128]
;               //
缓存
     printf
(\"
输入数字: \"
);
     scanf
(\"%d\"
,&num
);
     itoa
( buf
, num
);
     printf
(\"
转换的字符串:%sn\"
, buf 
);
     return 0
;
}
//
数字-
字符转换函数
void itoa
(char *buf
, int num
)
{
      int i=0
;
      //
数字转换为倒序的字符串
      do
      {
            buf[i] = num % 10 + \'0\'
;     //
加数字0
的值完成转换
            i++
;
            num /= 10
;
      }while
(num 
!=0
);
      buf[i]=\'\0\'
;                    //
添加结束符
      printf
(\"
逆序:%sn\"
,buf
);          //
验证信息
      reverse
(buf
, i
);               //
反序
}
void reverse
( char buf
, int i
)
{
     int j=0
;
     //
字符串反序
     for
(j=0
; j<i/2
; j++
)
           swap
( &buf[j]
, &buf[i-1-j]
);
}
void swap
( char *a
, char *b
)
{
      char temp
;
      temp = *b
;
      *b = *a
;
      *a = temp
;
}
  

运行示范如下:


输入数字: 
10250986
逆序:68905201
转换的字符串:10250986
  

swap函数应该使用指针传递参数,调用使用地址符&。如果设计为如下形式:


void swap
( char a
, char b
)
{
      char temp
;
     temp = b
;
      b = a
;
      a = temp
;
}
  

则实现不了。可以定义为宏,则不用使用&传递参数。为了简单,直接将宏定义在reverse函数里。下面使用宏定义swap函数,程序中给出两种方式:位运算和使用临时变量进行交换。其实,也可以不使用临时变量,直接对变量进行运算实现交换。在程序中注释掉一种,使用位运算实现交换。下面是程序实现和运行示范。


#include <stdio.h>
void itoa
(char *buf
, int num
);          //
转换函数
void reverse
( char buf
, int i
);          //
反转函数
int main
()
{
     int num = 0
;                    //
接受键盘输入应初始化为0
     char buf[128]
;                     //
缓存
     printf
(\"
输入数字: \"
);
     scanf
(\"%d\"
,&num
);
     itoa
( buf
, num
);
     printf
(\"
转换的字符串:%sn\"
, buf 
);
     return 0
;
}
//
数制转换函数内部使用宏定义swap
void itoa
(char *buf
, int num
)
{
     int i=0
;
     //
数字转换为倒序的字符串
     do
     {
             buf[i] = num % 10 + \'0\'
;     //
加数字0
的值完成转换
             i++
;
             num /= 10
;
     }while
(num 
!`=0
);
     buf[i]=\'\0\'
;                    //
添加结束符
     printf
(\"
逆序:%sn\"
,buf
);          //
验证信息
     reverse
(buf
, i
);                    //
反序
}
//
定义反序函数reverse
void reverse
( char buf
, int i
)
{
    int j=0
;
    #if 0
    //
定义交换宏实现反转
    #define SWAP
(a
,b
) do{a=
(a
)+
(b
); 
                        b=
(a
)-
(b
); 
                        a=
(a
)-
(b
); 
                        }while
(0
)
    #endif
    //
使用异或定义交换宏,异或运行快(加法要有进位操作)
    #define SWAP
(a
,b
) do{a=
(a
)^
(b
); 
              b=
(a
)^
(b
);           
              a=
(a
)^
(b
);           
                 }while
(0
)
    //
字符串反序
    for
(j=0
; j<i/2
; j++
)
           SWAP
( buf[j]
, buf[i-1-j]
);
}
输入数字: 
30257890
逆序:09875203
转换的字符串:30257890
  

函数设计要在能完成功能的前提下,尽量简单。尽可能设计为void类型,也是出于这个考虑。

另外,要注意传结构参数时,是要整体复制结构体的数据。如果结构很大,例如结构里有很大的数组,这种复制是很费时的。同样,如果返回值是结构,也需要将结构值整体复制到函数外。为了避免这种费时的操作,常传递结构的指针(它们的地址值),返回也是一样。

尤其要注意字符串常量与字符串数组的区别,字符串常量是分配在全局文字常量区,传递效率高。

注意使用一些算法技巧来简化函数设计,如在第17章的例17.10和例17.11中,用构造不同的数进行位运算以解决统计一个数的二进制中包含1的个数问题。其实,还可以构造出一些特殊数字来简化求解过程并提高求解的速度。另外,还可以使用一些编程技术提高程序性能,如状态机等技术。

【例25.6】编写统计一个数的二进制中包含1的个数的程序。

第17章的两种编程方法都是使用比较的方法,效率较低。现在使用加法运算。编写时一般先求正确,正确之后再求优化,不要优化过早,以免进入歧路。

现在先以0xff为例,构造一个数0x55,0x55的特点是01相隔。把两者进行与运算。在结果一行中的注释符号里把它们用序号编号并记为第1次&结果。


  1111 1111
& 0101 0101
  0101 0101     // 
(1
) 
第1
次&0x55
的结果
  

“0xff&0x55=0x55”。解释一下结果的含义:结果里的1的含义是0xff如果偶数位有1,则这2位里的数字就是1(01),由此可知结果代表有4个1。

将0xff右移“0xff>>1”,还是0xff,再与0x55进行&运算。


  1111 1111 >>1  //0xff
右移,  0xff>>1
& 0111 1111      //
再&0x55  
第1
次与
  0101 0101      //
(2
) 
第2
次&0x55
的结果
  

这即相当于把奇数位的1保留,也是4个1。

将两次二进制数相加,即


  0101 0101    //
(1
)
+ 0101 0101    //
(2
)
  1010 1010    //
(3
) 
第1
轮结果
  

二进制两两相加时,不要把它看做一个数,而是表示两位代表1的个数相加。即原来两位表示1的个数(二进制)相加,现在的2位就是代表具有几个1(只能是0或1,2)。上面的结果表明每两位都是2,下面就是要考虑如何将4个2相加,使其结果代表总共具有的1的位数是8位。

现在的运算结果的十六进制是0xaa,下面进行第二轮操作。这次操作使用0x33,用它与(3)进行&操作。


  0011 0011    //
构造一个数0x33
& 1010 1010    //&
(3
)
  0010 0010    // 
(4
) 
第1
次&0x33
的结果
  

与第1轮一样,要将(3)的结果移位后再&0x33,但这次是移2位。


  0010 1010   //
将(3
)的结果0xaa>>2
& 0011 0011   //0x33
  0010 0010   // 
(5
) 
第2
次&0x33
的结果
  

进行(5)+(6)运算。


  0010 0010   //
(4
)
+ 0010 0010   //
(5
)
  0100 0100   // 
(6
)
  

经过两轮得到0x44,第3轮要计算4+4=8,再构造0xf(0000 1111)。与前两轮的方法一样,继续做下去。用0x44,选择0xf进行第3轮如下:


  0000 1111   //
构造一个数0xf
& 0100 0100   // 
(6
)
  0000 0100   //
(7
) 
第1
次&0xf
的结果
  0000 0100    //
将(6
)>>4
& 0000 1111    //0xf
  0000 0100   //
(8
) 
第2
次&0xf
的结果
+ 0000 0100   //
(7
)
  0000 1000   //
( 8
)+
(7
) = 8
  

由此得出8位的编程方法。固定次数8bit用到2的3次方,先定义3个常量。


#define M1 0x55
#define M2 0x33
#define M3 0x0f
  

对给定的num,将上述3个步骤写出如下的公式。


(num & M1
) + 
((num >> 1 
) & M1
)
(num & M2
) + 
((num >> 2 
) & M2
)
(num & M3
) + 
((num >> 4 
) & M3
)
  

根据如上公式,编写如下程序。


#include <stdio.h>
#define M1 0x55
#define M2 0x33
#define M3 0x0f
int main
()
{
     int number
, num=0
;
     printf
(\"
输入数字: \"
);
     scanf
(\"%d\"
,&number
);
     num=number
;
     num = 
(num & M1
) + 
((num >> 1
) & M1
);
    printf
(\"num=%#xn\"
, num
);
    num = 
(num & M2
) + 
((num >> 2
) & M2
);
    printf
(\"num=%#xn\"
, num
);
    num = 
(num & M3
) + 
((num >> 4
) & M3
);
    printf
(\"num=%#xn\"
, num
);
    printf
(\"%d 
含有%d
个1n\"
, number
, num
);
    return 0
;
}
  

使用255验证上述算法,第1次是0xaa,第2次是0x44,第3次是0x8,即8个1。


输入数字: 
255
num=0xaa
num=0x44
num=0x8
255 
含有8
个1
  

32位要定义M4和M5,并构造5个常量。


//32
位程序
 #include <stdio.h>
 #define M1 0x55555555
 #define M2 0x33333333
 #define M3 0x0F0F0F0F
 #define M4 0x0FF00FF
 #define M5 0x0000FFFF
 int main
()
 {
      int number
, num=0
;
      printf
(\"
输入数字: \"
);
      scanf
(\"%d\"
,&number
);
      num=number
;
      num = 
(num & M1
) + 
((num >> 1 
) & M1
);
      num = 
(num & M2
) + 
((num >> 2 
) & M2
);
      num = 
(num & M3
) + 
((num >> 4 
) & M3
);
      num = 
(num & M4
) + 
((num >> 8 
) & M4
);
      num = 
(num & M5
) + 
((num >> 16
) & M5
);
      printf
(\"%d 
含有%d
个1n\"
, number
, num
);
      return 0
;
}
 

运行示范如下:


输入数字: 
65535
65535 
含有16
个1
输入数字: 100
100 
含有3
个1
输入数字: 0
0 
含有0
个1
  

程序中去掉了打印每次结果的信息,这个程序很确定,不足之处是0也要5次,但也是很确定的5次,所以也是可以的。

很多程序还要受到条件的影响,约瑟夫环就是典型的例子。根据要求,可以使用一维数组、二维数组、结构、动态内存、链表、循环链表等手段编写求解程序。可以参考拙作《C程序设计课程设计(第2版)》(机械工业出版社)。

《C语言解惑》