【笔试常见编程题06】最近公共祖先、求最大连续bit数、二进制插入、查找组成一个偶数最接近的两个素数

1. 最近公共祖先

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
测试样例：
2，3
返回：1
示例 1
输入
输出

思路1:
节点除2就是parent
大的先除直到两个数相等

class LCA {
public:int getLCA(int a, int b) {while (a != b) { if (a > b) a /= 2;else b /= 2;}return a;}
};

2. 求最大连续bit数

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
数据范围：数据组数：1 ≤ t ≤ 5, 1 ≤ n ≤ 500000
进阶：时间复杂度：O(logn)空间复杂度：O(1)
输入描述
输入一个int类型数字
输出描述
输出转成二进制之后连续1的个数
示例 1
输入
200
输出
2
说明
200的二进制表示是11001000，最多有2个连续的1

思路1:
从右往左找连续的1
更新计数器，直到找到最长的连续的1

int main() {int a = 0, count = 0;while (cin >> a) {int temp = 0;for (int i = 0; i < 32; i++) {if (1 << i & a)temp++;if ((1 << i & a) == 0 || i == 31) { //如果a=-1,二进制全是1,需要加一个条件i == 31就进来count = max(temp, count);  temp = 0;}     }cout << count << endl;}return 0;
}

思路2:
求二进制数有几个1，n & n-1
求二进制数最长连续的1，n & (n << 1)

int main() 
{int n;while (cin >> n) {int count = 0;while (n) {n = n & (n << 1);count++;}cout << count << endl;}return 0;
}

3. 二进制插入

给定两个32位整数n和m，同时给定i和j，将m的二进制数位插入到n的二进制的第j到第i位,保证n的第j到第i位均为零，且m的二进制位数小于等于i-j+1，其中二进制的位数从0开始由低到高。
测试样例：
1024，19，2，6
返回：1100
示例 1
输入
输出

思路1:

class BinInsert {
public:int binInsert(int n, int m, int j, int i) {m <<= j;return n + m;}
};

class BinInsert {
public:int binInsert(int n, int m, int j, int i) {while(j) {m *= 2;j--;}return n + m;}
};

4. 查找组成一个偶数最接近的两个素数

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。
数据范围：输入的数据满足
输入描述
输入一个大于2的偶数
输出描述
从小到大输出两个素数
示例 1
输入
20
输出
7
13
示例 2
输入
4
输出
2
2

思路1:
中间组成偶数的两个素数差值最小
从中间往两边找差值最小素数

#include <iostream>
using namespace std;// 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数
bool isPrime(int n) { // 经常用到的功能封装成函数会更方便for (int i = 2; i <= n / 2; i++) {if (n % i == 0)return false;}return true; // 遍历完都没有就是素数
}int main() { int n;while (cin >> n) {for (int i = n/2; i > 0; i--) if (isPrime(i) && isPrime(n - i)) {cout << i << '\n' << n - i << endl;break;}}return 0;
}