1, 整数表示

一,布尔代数表示

0UL--------无符号长整型0

1UL--------无符号长整型1

1, 位运算

a = [0110], b = [1100]

1. &

     0110
    &1100
     0100

2. |

     0110
    |1100
     1110

3. ^

     0110
    ^1100
     1010

4. ~

    ~1100
     0011

2, 分配侓

1. 布尔运算侓 & 对 | 的有分配侓
2. 布尔运算侓 | 对 & 的有分配侓

a * (b + c) = (a + b) + (a + c) ==> a & (a | b) = (a & b) | (a & c)  

位向量一个很有用的应用就是表示有限集合。我们可以用位向量
[, ..., ]编码任何子集A {0, 1, ..., w - 1}, 其中 = 1 当且仅当 A 。 例如(记住是把 写在左边， 而将 写在右边。), 位向量 a = [01101001]表示集合 A = {0, 3, 5, 6}, 而 b = [01010101] 表示集合 B = {0, 2, 4, 6}。 使用这种编码集合的方法， 布尔运算 | 和 & 分别对应于集合的并和交， 而 ~ 对应于于集合的补。

还是分配侓a&b得到位向量[01000001], 而 A B = {0, 6}

3, 运用位级计算

void inplace_swap(int *x, int *y)
{
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

1. 交换数组中第一元素和最后一个元素

void reverse_array(int a[], int cnt)
{
    int first, last;
    for (first = 0, last = cnt - 1; first <= last; ++first, --last)
    {
        inplace_swam(&a[first], &a[last]);
    }
}

上面代码有一个问题 就是奇数时会错误

cnt = 2k - 1

4, 移位运算

位的表示 A = [, , ... , ]

1, 左移(<<)

A << k [, , ... , , 0, 0, ]

2, 右(>>) --有点奇葩

分为两种情况:

<font color = red>

1. 逻辑右移
2. 算术右移

</font>

• 逻辑右移

右移在左端补k个0

A >> k [0, 0, 0, , , , ... , ]

• 算术右移

算术右移在左端补k个最高位有效的值

A >> k [, , ..., , , , ... , ]

看一下实例

操作	值
参数	[0110 0011] [1001 0101]
x << 4	[0011 0000] [0000 0101]
x >> 4 (逻辑右移)	[ 0110] [ 1001]
x >> 4 (算术右移)	[ 0110] [ 1001]

5.1,整数表示

描述位来编码整数的两种不同的方式：

<font color = red>

一种只能表示非负数， 二别一种能够表示负数, 零和整数
</font>

下面是一些术语

符号	类型	含义
	函数	二进制转补码
	函数	二进制转无符号数
	函数	无符号数转换二进制
	函数	无符号数转换补码
	函数	补码转二进制
	函数	补码转无符号数
	常数	最小补码值
	常数	最大补码值
	常数	最大无符号数
	操作	补码加法
	操作	无符号数加法
	操作	补码乘法
	操作	无符号数乘法
	操作	补码取反
	操作	无符号数取反

<font color = red>
下标w表示数据表示中位数
</font>

5.2 整数数据类型

32位机器

C数据类型	最小值	最大值
[signed] char	-128	127
unsigned char	0	255
short	-32768	32767
unsigned short	0	65535
int	-2147483648	2147483647
unsigned int	0	4294867295
long	-2147483648	2147483647
unsigned long	0	4294967295
int32_t	-2147483648	2147483647
uint32_t	0	4294867295
int64_t	-9224472036854775808	9224472036854775807
uint64_t	0	18446744073709551615

C/C++都是支持有符号(默认)和无符号数。 Java只支持有符号数

5.3 无符号数的编码

有一个整数类型是有w位，我们可以将位向量写成 , 表示整个向量， 或者[, , ... , ], 表示向量中每一位。把 看做一个二进制表示的数， 就获取了 的表示。在整个编码中国， 每个位 都取值为0或1， 我们使用一个函数

原理： 无符号数编码的定义

对向量 [, , ..., ]

() ==

下面是几种情况

([0001]) = 0 * + 0 * + 0 * + 1 * = 0 + 0 + 0 + 1 = 1

([0101]) = 0 * + 1 * + 0 * + 1 * = 0 + 4 + 0 + 1 = 5

([1011]) = 1 * + 0 * + 1 * + 1 * = 8 + 0 + 2 + 1 = 11

([1111]) = 1 * + 1 * + 1 * + 1 * = 8 + 0 + 2 + 1 = 15

矢量