信息的表示和处理

信息的表示

  1. 什么是字节(byte)? 什么是字(word)

    字节: 最小可寻址的存储器单元
    : 整数和指针数据的标称大小(normal size)

  1. 熟悉十六进制
十六进制 十进制 二进制
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111
  1. 数据的大小
C 类型 32位机器 64机器
char 1 1
short int 2 2
int 4 4
long int 4 8
long long int 8 8
char* 4 4
float 4 4
double 8 8
  1. 字节序

 小端: 从最低有效字节到最高有效字节顺序存储
大端: 反之

确定大小端的方法:

1
2
3
4
5
6
7
8
9
10
union A  
{
char c;
int a;
}A;
A.a = 1;
if(A.c == 1)
return little_endian;
else
eturn big_endian;
  1. 布尔代数与位级运算

布尔代数:

AND OR NOT EXCLUSIVE-OR
& \ ^ ~

移位操作: <<, >>

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”,

Return:
[“AAAAACCCCC”, “CCCCCAAAAA”].

  1. 整数的表示

无符号数的编码

$$
B2U_w(x) := \sum_{i=0}^{w-1} x_i2^i
$$

补码编码

$$
B2T(x) := -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i
$$

有符号数和无符号数之间的转换

  1. 什么情况下是安全的

    • 相同字长的情况
    • 不同子长的情况
  2. 边界检查的巧妙利用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /// 如何检查当前坐标是否超出图像
    int row, col;

    if( row >= 0 && row < height && col >=0 && col < width){

    }

    if( (unsigned)row < height && (unsigned)col < width){

    }
    ///

 字面变量的默认类型后缀 ‘U’, ‘u’

1
2
1234;
0x1A2B;

如果操作数一个是有符号另一个是无符号的, C语言会隐式地将有符号参数轻质转换为无符号数, 并假设这两个数都是非负的来执行这个运算

警惕不同符号数的比较

1
-1 < 0U;
  1. 不同长度整型的转换, 截断

    sum_elements(float a[], unsigned length)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
         {
    int i;
    float result = 0;
    for(i = 0; i <= length -1; i++)
    result += a[i]
    return result;
    }



    7. 浮点数



    ``` c++
    inline void binary16_encode(const float* f32, uint16_t* f16)
    {
    const uint32_t& u32 = *(uint32_t*)(f32);
    uint16_t& u16 = *f16;
    int ex = ((u32 & 0x7f800000) >> 23);
    ex = std::max(0, std::min(ex - 0x7f + 0x0f, 0x1f));
    u16 = ((u32 & 0x80000000) >> 16) + (ex << 10) + ((u32 & 0x007fffff) >> 13);
    }

    inline void binary16_decode(const uint16_t* f16, float* f32)
    {
    uint32_t& u32 = *(uint32_t*)(f32);
    const uint16_t& u16 = *f16;
    int ex = ((u16 & 0x7c00) >> 10);
    ex = std::max(0, std::min(ex - 0x0f + 0x7f, 0xff));
    u32 = ((u16 & 0x8000) << 16) + (ex << 23) + ((u16 & 0x03ff) << 13);
    }

Reference