听课笔记——《二进制入门》

一、二进制规则

1. 逢二进一

一位数字中只有0和1两种可能。

2. 尾数为0是偶数(even)；尾数为1是奇数(odd)

大于一位二进制数减去其末位上的数字后必然是2的乘方或2的乘方和，可以被2整除，所以必然是一个偶数。加上末位上的数字后，若末位数字是1，则该数为偶数加1为偶数加1，为奇数；若末位数字是0，则结果不变，为偶数。
我觉得类似于十进制中，大于一位的十进制数减去其末位上的数后为10的乘方或10的乘方和。因此，若末位数字为0，则该数能被10整除（是10的整数倍）；反之，若末位数字非0，则不能被10整除。

3. 任意一个二进制数尾部添一个0，结果等于原数乘二

二进制数额外添加一个末位数字0，我觉得相当于其每一个数位上的数值不变但都往左移了一位，所以每一位所表示的数值都是之前的两倍，最后整个二进制数也变为原来的两倍。
类似于十进制中，任意十进制数字额外在末位添加一个0，结果等于原数乘十（相当于每一位数所表示的数值都是原来的十倍）。

4. 任意一个二进制数 100…0(i个0) = 2ⁱ(2的i次幂); 11…1(i个1) = 100…0(i个0) - 1 = 2ⁱ - 1

另：2¹⁰ = 1024

二、课堂练习

1) 1 + 2 + 2² + 2³ + … + 2¹⁰

法一：等比数列求和公式
法二：原式 = 1(2) + 10(2) + 100(2) + 1000(3) + … + 100…0(10个0) = 111…1(10个1) = 100…0(11个0) - 1 = 2¹¹ - 1 = 2048 - 1 = 2047

2) 十进制转二进制

假设一个十进制数为D
第一步：可以知道D如果表达为二进制最后一个比特的数值（偶数是0，否则为1）
第二部：处理剩下的数位，去掉最后一个比特（右移一位，相当于D整除2），然后重复第一步（递归调用）

// 以下是使用c++的实现，其中我用字符串来表示目标二进制数，只能处理0和正整数
string Dec2Bin(int d)	// 需要使用到string类
{string b{};if (d <=1) {	// 递归调用结束条件if (d) {return "1";} else {	// 处理d原本为0的情况return "0";}}b = Dec2Bin(d >> 1);	// 记录d向右移一位(除以二)后作为参数递归调用函数的返回值if (d % 2) {	// 将此次递归调用的结果(0或1)连接到字符串末位return b + "1";} else {return b + "0";}return b;
}

另记（位操作）：
~：按位取反
&：按位与，同时为一结果才是1，否则结果为0
^：按位异或，不同为1，相同为0
|：只要有至少一个1结果就是1，否则结果为0

3) 不使用"+"实现整数加法

// c/c++函数实现
int myAdd(int a, int b)
{if (!b) {return a;} else {return myAdd(a ^ b, (a & b) << 1);// 这里(a ^ b)处理两数在相同的二进制位上有且仅有其中一个为1的情况，为非进位情况。具体为其中一个数一个数位上的0加上另一个数相同数位上的1// ((a & b) << 1) 处理两数相同二进制位上都为1的进位情况，不是同为1的数位则不做处理(变为0)，保留相应数位上的1后向左移动一位即相当于完成了二进制数的进位// 将上述两个运算后得到的结果分别作为两个实际参数递归调用myAdd函数，当递归到参数b为0时，a即为所求(两数相加的结果)}
}

4) 不使用"*"实现整数乘法

// c/c++实现
// 使用累加整数a进行计算，时间复杂度为b
int myMul1(int a, int b)
{if (!b) {return 0;} else {return a + myMul1(b - 1);}
}// 使用(a * b = 2 * a * (b / 2))进行递归计算，时间复杂度为log(b)
int myMul2(int a, int b)
{if (!b) {return 0;} else {if (b % 2) {	// 因为下面(b / 2)是整除，所以若b为奇数则需要另外加上漏掉的一个areturn myMul2(a, b / 2) + myMul2(a, b / 2) + a;} else {return myMul2(a, b / 2) + myMul2(a, b / 2);}}
}

三、课后作业

#include 
#include 
#include bool is_even(int);
void prt_binary(int);
int binary_reverse(int);
int add(int, int);
int mul(int, int);
int calBinDigits(int);  // 计算传入参数的二进制位数int main()
{int n, a, b;printf("Please input three integers(n, a, b): ");scanf("%d %d %d", &n, &a, &b);printf("is_even(n): %d\nbinary_reverse(n): %d\nadd(a, b): %d\nmul(a, b): %d\n", is_even(n), binary_reverse(n), add(a, b), mul(a, b));printf("prt_binary(n): ");prt_binary(n);  // 打印n的二进制比特return 0;
}bool is_even(int n)
{if (n % 2) {return false;} else {return true;}
}void prt_binary(int n)  // 只处理0和正整数
{if (n <=1) {if (n) {printf("1");} else {printf("0");}} else {prt_binary(n >> 1);	// 先进行递归再打印相应的二进制数，让高位上的数字先打印出来(打印在低位数字的前面)printf("%d", n % 2);}
}int binary_reverse(int n)
{int digit, target_n = 0;    // digit表示整形变量n转化为二进制数时的有效位数，target_n为所求的比特倒叙排列后相应的整数digit = calBinDigits(n);for (digit--; digit >=0; digit--, n /=2) {target_n += pow(n % 2 * 2, digit);}return target_n;
}int add(int a, int b)
{if (!b) {return a;} else {return add(a ^ b, (a & b) << 1);    // (a ^ b)处理相同数位上其中一个为0，另一个为1的情况，即(0 + 1)，非进位；((a & b) << 1)处理相同数位上两数都为1的情况，其他情况的数位则把数值变为0，只计算需要进位的数位，同时右移一位完成进位}
}int mul(int a, int b)
{if (!b) {return 0;} else {if (b % 2) {    // 因为下面使用的是整除，所以如果b是奇数的话换少计算一个a，需要把加上漏算areturn 2 * mul(a, b / 2) + a;   // 奇数} else {return 2 * mul(a, b / 2);   // 偶数}}
}int calBinDigits(int n) {int digit;for (digit = 0; n >=pow(2, digit); digit++);return digit;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！