Category: Computer Science

参考资料：
http://en.wikipedia.org/wiki/Exponential-Golomb_coding
http://zh.wikipedia.org/zh/指数哥伦布码
Information technology — Coding of audio-visual objects — Part 10: Advanced Video Coding

摘抄自以上资料，简单总结。

指數哥倫布碼(Exp-Golomb code)，一种壓縮編碼方法。
用来表示非负整数的k阶指数哥伦布码可用如下步骤生成：
1. 将数字以二进制形式写出，去掉最低的k个比特位，之后加1
2. 计算留下的比特数，将此数减一，即是需要增加的前导零个数(注意是比特位数，非该比特串表示的值)
3. 将第一步中去掉的最低k个比特位补回比特串尾部
0阶指数哥伦布码如下所示：

0 => 1 => 1
1 => 10 => 010
2 => 11 => 011
3 => 100 => 00100
4 => 101 => 00101
5 => 110 => 00110
6 => 111 => 00111
7 => 1000 => 0001000
8 => 1001 => 0001001
...

从二进制比特串形式来看，0阶哥伦布编码的码字(codeword)由3部分构成：
码字 = [M个0] + [1] + [内容]
内容也是M位数据，所以每个0阶哥伦布码的位的长度为2M + 1，每个码字由原始的数字(codenumber)产生。

比如上面的数字7，二进制表示为111，0阶编码，所以不用去最后的比特为，加1之后变成1000，比特数为4位，所以前缀需要增加3(4-1)个0，即0001000，0阶所以结尾也不需要补码，于是最终码字就为0001000。

那如何解码呢？
参见如下伪代码

leadingZeroBits = −1
for (b = 0; !b; leadingZeroBits++)
	b = read_bits(1)

codeNum = 2^(leadingZeroBits + k) − 2^k + read_bits(leadingZeroBits + k)

这里类似于2^k这种写法表示幂运算，对于通常H.264当中用的是0阶的，所以可以简化成如下图

这里read_bits(…)的返回值使用高位在先的二进制无符号整数表示

二进制比特串       长度             解析值
1001             1               0
001 1001         5               5
01 1010          3               2
010              3               1
000 1011         7               10
0001 001         7               8

如上表，传入的比特串可能多余实际需要的数据，我们只需要解析需要的部分就可以了。

P.S.
为什么叫做指数哥伦布编码？
因为它对信源符号的分组大小按照指数增长。

炒现饭的帖子，内容均来自于网络或者书籍整理。

I)树
它是由N(N>=1)个有限结点组成一个具有层次关系的集合，它具有以下的特点：
a)每个结点有零个或多个子结点，没有子节点的节点称为叶节点(通常称为叶子)
b)没有父结点的结点称为根结点(通常称为根)
c)每一个非根结点有且只有一个父结点(没有多个引用指向同一个节点)
d)除了根结点外，每个子结点可以分为M个不相交的子树

|
r        55
o       /  \
o      /    \
t     88     3
.           /|\
.          / | \
.         67 7 23
l        / \     \
e       /   \     \
a      53    5     9
f
|

        Figure. A

如上图(Figure. A)，它像一棵自然界中倒生长的树，每个枝丫处就是一个节点，方向是由根到叶子，它实际上是一个有向图。

这里我们介绍下节点，节点是包含一个数据项和一个(多个)指向其他节点的引用项的数据结构/记录，通常我们用类似如下代码来表示一个节点：
1)

record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
}

2)

record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
}

3)

record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
}

结合上图(Figure. A)我们就很好理解了。

一些有关树的基本概念：
节点的度(node’s degree): 子节点的个数叫做节点的度
树的度: 一棵树中，最大的节点的度称为树的度
节点层次(level): 根为第一层，根的子节点为第二层，以此类推
数的高度或深度(depth): 树中最大的节点层次
兄弟节点(siblings): 具有相同父节点的节点
森林: M(M>=0)棵互不相交的树的集合(删去一棵树的根，就得到一个森林；加上一个结点作树根，森林就变为一棵树)
有序树(ordered tree)/无序树(unodered tree): 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(ordered tree)；否则称为无序树(unodered tree)
还有诸如子孙/祖先/堂兄弟节点这些概念就不列举了

上图(Figure. A)当中，树的度是3，67节点的度是2，数的深度是4，55节点是根节点等等这些基本属性我们就能很快得出。

II)二叉树
每个结点最多有两个子树的有序树，通常有左子树(left subtree)和右子树(right subtree)，最大的节点的度为2，也就是二叉树的度为2。

满二叉树(full binary tree): 有时被称为proper binary tree或者2-tree或者strictly binary tree，就是每个节点有0或2个子节点。

完全二叉树(complete binary tree): 除了最后一层之外的其他层次(当然也可能包含最后一层)，每个节点都包含2个子节点，并且所有节点都尽可能靠左排列

平衡二叉树: 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树

二叉树的遍历，前序(pre-order)，中序(in-order)和后序(post-order)，前序是根左右，中序是左根右，后序是左右根。

一些有关二叉树的常用算法参看http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

几个简单的例子:

这里的代码实现都是简单易懂的实现，帮助理解概念，没有做过优化！

参考资料:
http://en.wikipedia.org/wiki/Tree_(data_structure)
http://en.wikipedia.org/wiki/Node_(computer_science)
http://en.wikipedia.org/wiki/Branching_factor
http://en.wikipedia.org/wiki/Binary_tree

http://zhedahht.blog.163.com/blog/static/25411174201142733927831/

又是一篇炒现饭的帖子，主要是经常忘记，记在这里

首先理解位bit(Binary digit http://en.wikipedia.org/wiki/Bit)

以下都以二进制为例

比如一个8位的存储单元，那么它就可以保存256种不同状态，如果是无符号数的话，那么就是0 ~ 2^8-1，即00000000 ~ 11111111

那么对于有符号的数就是-2^7 ~ 2^7-1，最高位拿来存储符号了，0为正，1为负，即10000001 ~ 01111111

十进制	原码	反码	补码
127	01111111	01111111	01111111
-127	11111111	10000000	10000001
128	010000000	010000000	010000000
-128			10000000
45	00101101	00101101	00101101
-45	10101101	11010010	11010011
1	00000001	00000001	00000001
-1	10000001	11111110	11111111

上表中红色的数是表示溢出的，8位的存储空间无法表示这样的有符号数

计算机中的有符号数都是以补码的形式存放的，可以理解为只有有符号数才有原码，反码，补码
正数的原码，反码，补码表示都一样
负数的原码为其绝对值的原码，但符号位为1；反码就是保持原码的符号位不变，其他位按位取反；补码就是反码加1

引用Wikipedia
“一个数字的二补数就是将该数字作位反相运算（即一补数），再将结果加 1，即为该数字的二补数。”

为什么要引入原码，反码，补码这些概念
参见：http://dev.csdn.net/htmls/17/17680.html

我们最需要关注的是补码，引用作者的原话是
“
补码的设计目的是:
⑴使符号位能与有效值部分一起参加运算，从而简化运算规则
⑵使减法运算转换为加法运算，进一步简化计算机中运算器的线路设计
”

引用自http://zh.wikipedia.org/wiki/二補數
“在二补数系统中，一个负数就是用其对应正数的二补数来表示。”
00000100 4
11111011 按位取反
11111100 二补数(-4)

“减法可以用一个数加上另一个数的二补数来表示”
5
-4
———-
1

00000101
+11111100
———-
000000001

另外字节(Byte)，字(Word)，双字，四字，字长这些概念都需要理解

阮一峰有个帖子讲的也很清楚明了

参考

http://zh.wikipedia.org/wiki/原码
http://zh.wikipedia.org/wiki/反码
http://zh.wikipedia.org/wiki/二補數
http://en.wikipedia.org/wiki/One’s_complement
http://en.wikipedia.org/wiki/Two’s_complement