19.1 伪随机数生成器的例子

如果我们需要0～1的随机浮点数，最简单的方法就是用PRNG（伪随机数发生器），比如马特赛特旋转演算法可以生成一个随机的32位的DWORD。然后我们可以把这个值转为FLOAT类型，然后除以RAND_MAX（我们的例子是0xFFFFFFFF），这样，我们得到的将是0..1区间的数。 但是如我们所知道的是，除法很慢。我们是否能摆脱它呢？就像我们用乘法做除法一样（14章）。 让我们想想浮点数由什么构成：符号位、有效数字位、指数位。我们只需要在这里面存储一些随机的位就好了。 指数不能变成0（在本例里面数字会不正常），所以我们存储0111111到指数里面，这意味着指数位将是1。然后，我们用随机位填充有效数字位，然后把符号位设置为0（正数）。生成的数字将在1-2的间隔中生成，所以我们必须从里面再减去1。 我例子里面是最简单的线性同余随机数生成器，生成32位（译注：32-bit比特位，非数字位）的数字。PRNG将会用UNIX时间戳来初始化。 然后，我们会把float类型当作联合体（union）来处理，这是一个C/C++的结构。它允许我们把一片内存里面各种不同类型的数据联合覆盖到一起用。在我们的例子里，我们可以创建一个union，然后通过float或者uint32_t来访问它。因此，这只是一个小技巧，而且是很脏的技巧。

  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <time.h>
  4. union uint32_t_float
  5. {
  6.     uint32_t i;
  7.     float f;
  8. };
  9. // from the Numerical Recipes book
  10. const uint32_t RNG_a=1664525;
  11. const uint32_t RNG_c=1013904223;
  12. int main()
  13. {
  14.     uint32_t_float tmp;
  15.     uint32_t RNG_state=time(NULL); // initial seed
  16.     for (int i=0; i<100; i++)
  17.     {
  18.         RNG_state=RNG_state*RNG_a+RNG_c;
  19.         tmp.i=RNG_state & 0x007fffff | 0x3F800000;
  20.         float x=tmp.f-1;
  21.         printf ("%f", x);
  22.     };
  23.     return 0;
  24. };

清单19.1: MSVC 2010 （/Ox）

  1. $SG4232 DB ’%f’, 0aH, 00H
  2. __real@3ff0000000000000 DQ 03ff0000000000000r ; 1
  3. tv140= -4 ; size = 4
  4. _tmp$= -4 ; size = 4
  5. _main PROC
  6.     push ebp
  7.     mov ebp, esp
  8.     and esp, -64 ; ffffffc0H
  9.     sub esp, 56 ; 00000038H
  10.     push esi
  11.     push edi
  12.     push 0
  13.     call __time64
  14.     add esp, 4
  15.     mov esi, eax
  16.     mov edi, 100 ; 00000064H
  17. $LN3@main:
  18.     ; let’s generate random 32-bit number
  19.     imul esi, 1664525 ; 0019660dH
  20.     add esi, 1013904223 ; 3c6ef35fH
  21.     mov eax, esi
  22.     ; leave bits for significand only
  23.     and eax, 8388607 ; 007fffffH
  24.     ; set exponent to 1
  25.     or eax, 1065353216 ; 3f800000H
  26.     ; store this value as int
  27.     mov DWORD PTR _tmp$[esp+64], eax
  28.     sub esp, 8
  29.     ; load this value as float
  30.     fld DWORD PTR _tmp$[esp+72]
  31.     ; subtract one from it
  32.     fsub QWORD PTR __real@3ff0000000000000
  33.     fstp DWORD PTR tv140[esp+72]
  34.     fld DWORD PTR tv140[esp+72]
  35.     fstp QWORD PTR [esp]
  36.     push OFFSET $SG4232
  37.     call _printf
  38.     add esp, 12 ; 0000000cH
  39.     dec edi
  40.     jne SHORT $LN3@main
  41.     pop edi
  42.     xor eax, eax
  43.     pop esi
  44.     mov esp, ebp
  45.     pop ebp
  46.     ret 0
  47. _main ENDP
  48. _TEXT ENDS
  49. END

GCC也生成了非常相似的代码。 # 函数指针

函数指针是指向函数的指针，和其他指针一样，只是该指针指向函数代码段的开始地址。函数指针经常用作回调1。

典型的例子如下：

  1. C标准库的 qsort()2, aexit()3；
  2. *NIX OS的信号机制；
  3. 线程启动：CreateThread()(Win32)，pthread_create()(POSIX)；
  4. 其他更多的Win32函数，比如EnumChildWindows()5。
  5. qsort()函数是C/C++标准库快速排序函数。该函数能够排序任意类型的数据。qsort()调用比较函数。

比较函数被定义为如下形式：

int (*compare)(const void *, const void *)

我们稍作修改：

  1. /* ex3 Sorting ints with qsort */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. int comp(const void * _a, const void * _b)
  6. {
  7.     const int *a=(const int *)_a;
  8.     const int *b=(const int *)_b;
  10.     if (*a==*b)
  11.         return 0;
  12.     else
  13.         if (*a < *b)
  14.             return -1;
  15.         else
  16.             return 1;
  17. }
  19. int main(int argc, char* argv[])
  20. {
  21.     int numbers[10]={1892,45,200,-98,4087,5,-12345,1087,88,-100000};
  22.     int i;
  23.     /* Sort the array */
  24.     qsort(numbers,10,sizeof(int),comp) ;
  25.     for (i=0;i<9;i++)
  26.         printf("Number = %d",numbers[ i ]) ;
  27.     return 0;
  28. }