Lecture 02 Bits,Bytes, and Integer 位，字节和整型

只有宾夕法尼亚大学建立的第一台电子计算机 ENIAC 使用十进制进行了算数运算，它们使用十个电子管来表示每个数字。

Byte 字节

Byte = 8 bits

• 二进制：00000000 - 11111111
• 十进制：0 - 255 = 2^8 - 1
• 十六进制：00 - FF (1111=2^4 - 1 = 15 = F)

C 数据类型占用的字节：

位操作

布尔代数

• & and 且

• | or 或

• ~ not 非

• ^ xor(Exclusive-or) 异或
  A^B = 1, 当 A=1或者B=1时，但不是全部都为1

^ | 0  1
---------
0 | 0  1
1 | 1  0

集合的表现形式和操作

• 表现形式
  宽度为w (width)位的向量表示的子集： {0, …, w–1}
  如果j ∈ A (j 属于 A) ，则 第j位数 a = 1

操作示例：
01101001 { 0, 3, 5, 6 }
76543210
01010101 { 0, 2, 4, 6 }
76543210

操作：

• & Intersection （交集） 01000001 { 0, 6 }
• | Union （并） 01111101 { 0, 2, 3, 4, 5, 6 }
• ^ Symmetric difference（对称差） 00111100 { 2, 3, 4, 5 }
• ~ Complement（补集） 10101010 { 1, 3, 5, 7 }

C语言的逻辑操作

与位操作有些相似，不要搞混淆。

操作符：&&, ||, !
特性：

• 0 视为 “False”
• 所有非0的都视为 “True”
• 返回值都是 0 或 1
• 提前终止特性

位移操作

• 左移 x << y
  将位向量x左移y个位置。
  扔掉左边多余的部分。
  右边空位填0

• 右移 x >> y
  将位向量x右移y个位置。
  扔掉右边多余的部分。

逻辑右移：
左边空位填0

算术右移：
左边空位填充符号位

示例：

Argument x    : 10100010
x << 3        : 00010000
Log. x >> 2   : 00101000
Arith. x >> 2 : 11101000

整型

• 无符号类型 Unsigned
• 二进制补码 Two’s Complement
  符号位：0 表示正数， 1 表示负数。

补码：表示有符号数的最常用的方式，有符号数还有其他表示方式，但是补码是最常用的方式。

数值范围

• 无符号值
  UMin = 0 (000…0)
  Umax = 2^w -1 (111…1)

• 二进制补码
  TMin = -2^(w-1) (100…0)
  TMax = 2^(w-1) -1 (011…1)

-1 : 111…1

如下：

• 规律
  |TMin| = TMax + 1
  UMax = 2 * TMax + 1

• c程序
  limits.h 定义了一些边界值。

#include <limits.h>
ULONG_MAX
LONG_MAX
LONG_MIN

无符号与有符号数值

B: Binary 二进制，U: Unsigned 无符号， T: Two’s Complement 二进制补码

无符号与有符号的转换映射：

映射值示例：

4位为例，符号位为1时：符号位的值 + 其他位的值
二进制补码：-2^3 + 其他位的值 = -8 + 其他位的值
无符号：2^3 + 其他位的值 = 8 + 其他位的值
无符号 - 二进制补码 = 8 + 其他位的值 - (-8 + 其他位的值) = 16 = 2^4

• 二进制补码转换为无符号
  Umax = 2^w -1 (111…1)
  TMin = -2^(w-1) (100…0)
  TMax = 2^(w-1) -1 (011…1)
  

无符号与有符号在C中

• 默认整型为有符号
• 无符号用后缀U表示：0U, 123123U

转换：

• 显示转换

int tx, ty;
unsigned ux, uy;
tx = (int)ux;
uy = (unsigned) ty;

• 隐士转换
  在参数赋值和过程调用时可能发生。

ty = ux;  // 无符号赋值给有符号
uy = ty;

• 有符号无符号比较运算
  W = 32， TMIN = -2,147,483,648, TMAX = 2,147,483,647

常量1               常量2               比较结果    结果类型    
0                   0U                  ==          unsigned
-1                  0                   <           signed
-1                  0U                  >           unsigned
2147483647          -2147483647-1       >           signed	
2147483647U         -2147483647-1       <           unsigned
-1                  -2                  >           signed
(unsigned)-1        -2                  >           unsigned
2147483647          2147483648U         >           unsigned
2147483647         (int)2147483648U     >           signed

结论：无符号和有符号的运算，有符号转化为无符号进行运算和比较，结果为无符号。

代码验证结论：

#include <stdio.h>

void main() {
    int x = -7;
    unsigned int ux = 3;
    if (x > ux) {
        printf("signed -7 > unsigned 3");
    }
}

// output:
// signed -7 > unsigned 3

拓展和截断

拓展

前面填充数字。
结果不会改变。

• 无符号
  拓展字段用0填充。

• 有符号
  拓展字段用符号位填充。

    short int x = 15213;
    int ix = (int)x;
    short int y = -15213;
    int iy = (int)y;

x: 15213, 00111011 01101101
ix: 15213, 00000000 00000000 00111011 01101101
y: -15213 11000100 10010011
iy: -15213, 11111111 11111111 11000100 10010011

截取

截取前面的数字。
对于小数值结果不会改变，对于大数值结果可能会改变。

• 无符号
  直接截取，相当于进行模运算：x mod 2^k

• 有符号
  前面的符号位被截取。
  类似于模运算。

#include <stdio.h>

void main() {
    int x = 53191;
    short int ix = (int)x;
    int y = -53191;
    short iy = (int)y;
    printf("x: decimal=%d,Hex=%x, ",x,x);
    printfBinary(x);
    printf("ix: decimal=%d,Hex=%x, ",ix,ix);
    printfBinary(ix);
    printf("y: decimal=%d,Hex=%x, ",y,y);
    printfBinary(y);
    printf("iy: decimal=%d,Hex=%x, ",iy,iy);
    printfBinary(iy);
}

//输出一个数的二进制
printfBinary(int num,int w){
    unsigned mask;
    sscanf_s("%d", &num);
    mask = 1u << 31;
    for(;mask;mask>>=1){
        printf("%d", num&mask?1:0);
    }
    printf("\n");
}

// output
// x:  decimal=53191 ,Hex=cfc7    , 0000000000000000 1100111111000111
// ix: decimal=-12345,Hex=ffffcfc7, 1111111111111111 1100111111000111
// y:  decimal=-53191,Hex=ffff3039, 1111111111111111 0011000000111001
// iy: decimal=12345 ,Hex=3039    , 0000000000000000 0011000000111001