整数运算

信息存储

大多数计算机使用8位的块或者字节,作为最小的可寻址的内存单位,我们可以将内存视为一个非常大的字节数组

一个数据类型可以跨越多个字节数组,诸如int占据4个字节,longlong占据8个字节.

为了方便简写(二进制表示法过于冗长),我们习惯上也采用十六进制来简单表示二进制位

字长是机器一次可处理的二进制数字的数目。比如32位机器,一次可处理4个字节

字长决定的最重要的系统参数是虚拟地址的空间大小,也就是说对于一个字长为w位的机器而言,虚拟地址的范围为
$$2^{w}-1$$
。(原因:如果我的虚拟地址空间编址字长大于机器字长将会发生需要多次操作才能寻到一个地址 比如10位地址 8位机器字长 取址变困难了)

long不太一样

long根据机器字长的不同占用的字节数不同

寻址和字节顺序

当一个数据对象跨越多个字节,它的地址使用的是字节中的最小地址

两种字节存储法:数字的低位在前(小端) 数字的高位在前(大端)

大端法和小端法

以一个程序为例

#include<stdio.h>
typedef unsigned char *pointer;
void show_bytes(pointer stat,size_t len){
    size_t i;
    for( i =0;i<len;i++)
        printf("%p\t0x%.2x\n",stat+i,stat[i]);
    //15213-->3b6d 小端法
    puts("");
}
int main(){
    int a =15213;
    show_bytes((pointer)&a,sizeof(int));
}

此程序中show_byte函数是int类型数据所占据的四个字节里的每个字节中的数据打印出来

由于3b6d=15213显然我们的计算机(Intel产的)是采用小端法存储多字节类型数据

表示字符串

字符串的结尾是一个以null(其值为0)字符结尾的字符数组。输出一个字符串知道找到'\0'才结束

U T F-8是Unicode的一种类型,采用4字节表示所有字符

ASCII码只表示了常见的128个字符

表示代码

一个程序在不同的操作系统中最终生成的机器代码是完全不一样的

因此二进制代码在不同机器上是不兼容的

布尔代数

布尔运算可以扩展到位向量的运算,位向量就是固定长度为w，由0和1组成的串

位向量一个应用是表示有限集合

算法中有种方法叫做二进制枚举,采用的就是这种思想

给出长度为n的数组,求能否从中选出若干个,使他们的和为K.如果可以,输出:Yes,否则输出No

Input
第一行：输入N,K,为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9)
第二行：N个值，表示数组中元素的值(1<=a[i]<=10^6)
Output
输出Yes或No
Sample Input
5 13
2 4 6 8 10
Sample Output
No

C语言中的位级和逻辑运算和移位运算

注意一下逻辑运算符&&和||与它们对应的位级运算&和|之间的区别

一个很重要的规则

C语言的除法规则是向0取整的

C语言中右移一位就是除2吗?

C语言中-3>>1和-3/2
#include<stdio.h>
int main(){
    printf("%d\n",-3>>1);
    printf("%d\n",-3/2);
    return 0;
}
输出结果是:-2和-1

看书时发现此种差异,来源于C 语言除法的规则是向0取整

而右移位仅仅只是去掉末尾的1,向负半轴舍入,具体如何消除此种差异,后续会涉及到

一旦除法可以用移位代替的话,除法的运算时钟周期将大幅度减少,速度会快好几倍

整数运算

特殊的无符号数

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

具体无符号数带来的不便hh 在下面会涉及

一些不常见的数据类型

int32_t和int_64类型分别为4B和8B,不受机器影响,使用确定大小的整数类型很有用
size_t是unsigned long long类型(和机器字长一致)

具体的数据类型和它的最小值和最大值等到补码讲完再涉及

无符号的编码

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

B就是Binary二进制位

U就是Unsigned无符号哈

此式子就是二进制位表示为无符号数
$$他的最大值为2^{w}-1记为UMax_w,最小为0$$

有符号数的编码

有符号数的表示方法有三种

涉及到反码,原码和补码

原码:
$$B2S_w(\vec{x})=(-1)^{x_{w-1}}*(\sum_{i=0}^{w-2}x_i2^{i})$$
S就是Sign-Magnitude

可以看出 原码和无符号数唯一的差距在于最高位的含义不同

无符号数最高位有权值为
$$2^{w-1}$$
原码最高位只是代表正负

反码:

$$B2O_w(\vec{x})=-x_{w-1}{(2^{w-1}-1)}+(\sum_{i=0}^{w-2}x_i2^{i})$$
O就是One’s Complement

反码的最高位权值为
$$s=2^{w-1}-1$$
通俗理解为若最高位为1(负数),最高位权值为-s,若最高位为0(正数)，权值为0结果和正数原码一样了

当然这种复杂的定义暂且了解即可

重头戏还是补码

补码
$$B2T_{w}(\vec{x})=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$$
T是Two‘ s-complement

可以看出,最高位赋了一个负权,是和无符号数的最高位不同的地方
一些补码的性质:

• 补码具有唯一性

• 大概就是说一个补码只能表示一个数(在表示范围内),不会产生多个补码表示同一个数的情况

• 补码的一个特殊值

• 范围

$$对于一个编码为w为的补码,其表示的范围为 [-2^{w-1},2^{w-1}-1], 左边记为TMin_w右边记为TMax_w$$

• 特殊值
  $$-TMin_w是一个很特殊的值$$
  特殊的地方在于,首先整数的运算具有环属性,当一个数溢出时会绕着环运算
  $$-TMin_w表示的是2^{w-1},但是不在表示范围内溢出了$$

  $$2^{w-1}相当于2^{w-1}-1+1就是TMax_w+1根据环的属性,最终又绕回TMin_w$$

  ​ 推论:
  $$在C语言中int类型的变量x有x<=0 可以推出 -x>=0是错的$$

$$同样的在C语言中int类型的变量x,y若x>y也不能推出-x<-y$$