1、机器数
一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.
比如，十进制中的数 +3 ，计算机字长为8位，转换成二进制就是00000011。如果是 -3 ，就是 10000011 。
那么，这里的 00000011 和 10000011 就是机器数。
2、真值
因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位1代表负，其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131）。所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。
例：
0000 0001的真值 = +000 0001 = +1，
1000 0001的真值 = –000 0001 = –1。
二. 原码, 反码, 补码的基础概念和计算方法.
在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念.对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式.
- 原码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:
[1111 1111 , 0111 1111]
即
[-127 , 127]
原码是人脑最容易理解和计算的表示方式.
- 反码
反码的表示方法是:
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.
- 补码
补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.
转：
作者：张子秋
出处：http://www.cnblogs.com/zhangziqiu/
（c语言中移位运算只能用于整数，整数A左移1位得到的结果为A*2，右移1位为A/2取整)。
- 左移运算符
表示把
左移
位，最左边的
- 右移运算符
表示把
1. 如果数字是一个无符号数值，则用0填补最左边的
2. 如果数字是一个有符号数值，则用数值的符号位填补最左边
其中第二个的符号位是1。
常用m>>1表示m/2, m&1表示m%2。
- 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n)
{
++count;
n = (n-1) & n;
}
return count;
}
};
56、出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
- 解析： //方法：考虑异或运算，两个想等的数异或运算之后等于0，整个数组做异或运算，其中两个
//数字不一样的异或运算之后某一位肯定为1，按照这一位为1对数组做划分，使得两个子数组
//部分只各有一个出现一次的数字
//两个相同数字异或=0，一个数和0异或还是它本身。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if(data.empty() || data.size()<2) return;
int resultExclusiveOR = 0;
for(int i=0; i<data.size();++i)
resultExclusiveOR ^= data[i];
unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
*num1 = *num2=0;
for(int j=0; j<data.size();++j)
{
if(isBit1(data[j], indexOf1)) //按第indexOf1位是否为1划分数组
*num1 ^= data[j];
else
*num2 ^= data[j];
}
}
unsigned int FindFirstBitIs1(int num)
{
int indexBit=0;
//按位与，都为1的时候该位才为1，最低位是1，若num的该位也是1，结果为0，便是找到了；否则为1，继续循环
while(((num&1)==0) && (indexBit < 8 * sizeof(int)))
{
num= num >> 1;
++indexBit;
}
return indexBit;
}
//右移indexBit位，返回该位是否为1；
bool isBit1(int num, unsigned int indexBit)
{
num = num >> indexBit;
return (num & 1);
}
};
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- 如图：
；
image.png
class Solution {
public:
int jumpFloorII(int number) {
if(number ==1)
return 1;
return 2*jumpFloorII(number-1);
}
};
链接：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387?f=discussion
来源：牛客网
其实是隔板问题，假设n个台阶，有n-1个空隙，可以用0~n-1个隔板分割，c(n-1,0)+c(n-1,1)+...+c(n-1,n-1)=2^(n-1)，其中c表示组合。
有人用移位1<<--number，这是最快的。直接连续乘以2不会慢多少，编译器会自动优化。不过移位还是最有启发的！
class Solution {
public:
int jumpFloorII(int number) {
int a=1;
return a<<(number-1); //等价于2的（number-1）次方；
}
};
网友评论