收集了一些可能会用到的小算法。
判断字节序
在处理数据是常常会碰到字节序(Byte Endian)的问题
Linux下可以直接用Shell命令查看:
C语言版
1 2 3 4 5 6 7 8 9 10 11 12
| #include <stdio.h>
int main(void) { int test = 1; if (*(char *)&test) printf("Little endian!\n"); else printf("Big endian!\n"); return 0; }
|
其原理为:取整形变量test的地址强制转换为字符型指针 (char *)
,这个地址
就只指向一个字节的内存块,其为四个字节中的最低地址,最后取这一字节内存块的值。
如果系统字节序为Little endian,则保存1的那一位必定在这一字节中,其值为1;
若为Big endian,则低位取出来的值为0.
bash版
1
| echo -n I | od -to2 | head -n1 | cut -f2 -d" " | cut -c6
|
输出1为Little endian;
0为Big endian.
Python版
1
| python -c "import sys;print(0 if sys.byteorder=='big' else 1)"
|
写成脚本形式可以为:
1 2 3 4 5 6
|
from struct import pack if pack('@h', 1) == pack('<h', 1): print "Little Endian" else: print "Big Endian"
|
判断是否为2的次方
1 2 3 4 5 6
| #include <stdbool.h> // need c99 support
bool isPowerOfTwo (unsigned x) { return !(x & (x-1)); }
|
原理:一个数若为2的次方,其二进制形式最高位肯定为1,其余位都为0.那么该数减去1的话,得到的二进制表示则恰恰相反,
最高位为0,其余位为1.这样的话,就可以通过按位与来判断了。
产生一定范围内的随机数
最显然的办法就是::
产生0到N-1之间的随机数,但是很多随机数生成器在数字低位上并不是随机的。更好的办法是
1
| (int)((double)rand() / ((double)RAND_MAX + 1) * N)
|
看例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10
int main(int argc, char const *argv[]) { int a[N], b[N]; float c[N], d[N]; srand(time(NULL)); for (int i=0; i<N; i++) { a[i] = rand() % N; b[i] = (int)((double)rand() / ((double)RAND_MAX + 1) * N); c[i] = (float)rand() / ((float)RAND_MAX / N + 1);
printf("a[%d] = %d; b[%d] = %d; c[%d] = %f\n", i, a[i], i, b[i], i, c[i]); } return 0; }
|
输出::
1 2 3 4 5 6 7 8 9 10 11
| $ ./rand_test a[0] = 9; b[0] = 3; c[0] = 4.707045 a[1] = 4; b[1] = 5; c[1] = 1.947819 a[2] = 9; b[2] = 3; c[2] = 8.725301 a[3] = 1; b[3] = 6; c[3] = 2.441400 a[4] = 7; b[4] = 0; c[4] = 7.176581 a[5] = 1; b[5] = 2; c[5] = 5.303668 a[6] = 6; b[6] = 2; c[6] = 3.098936 a[7] = 0; b[7] = 3; c[7] = 5.129158 a[8] = 5; b[8] = 9; c[8] = 3.879813 a[9] = 3; b[9] = 6; c[9] = 7.315299
|
总结下来,要产生[M, N]之间的随机数,可以按照以下的公式::
1
| M + rand()/(RAND_MAX / (N-M+1) + 1)
|
参考
修改
- 2015-10-16: 初稿
- 2016-04-14: 增加随机数部分