7-19下午刷题未知点集合
接着上午有关 X&(X-1) 的另一个例题：
用一个表达式，判断一个数X是否是2N次方(2,4,8,16,…)，不可用循环语句。
［中国台湾某著名CPU生产公司2007年10月面试题］
解析：2、4、8、16这样的数转化成二进制是10、100、1000、10000。如果X减1后与X 做与运算，答案若是0，则X是2N次方。
答案：!(X&(X-1))
下午：
1.
基本的优先级需要记住：
指针最优，单目运算优于双目运算。如正负号。
先算术运算，后移位运算，最后位运算。
逻辑运算最后计算。
请特别注意：1 << 3 + 2 && 7等价于 (1 << (3 + 2))&&7.
例：
一是类型转换问题；二是算符的优先级问题。
对于第一个问题：
unsigned char b=~a>>4，在计算这个表达式的时候，
编译器会先把a和4的值转换为int类型（即所谓整数提升）后再进行计算，
当计算结果出来后，再把结果转换成unsigned char赋值给b。
对于第二个问题：
因为“~”的优先级高于“>>”和“+”，本题的过程是这样的：
先对于1010 0101取反0101 1010；再右移
这里有一个问题，是先右移4位再加1呢，还是直接右移5（4+1）位。
因为“+”的优先级高于“>>”，所以直接右移5位。结果是0000 0010。
最后的结果应该是2才对，但把如上的指令放到vs2008中运行，答案居然是250。
那么到底是什么地方出了问题？在调试的过程中进入汇编指令。可以看到高级语句转换为汇编语言以后，是 先执行取反 再位移 的。
我们看到eax是16位的寄存器，于是在机器中
0xA5的寄存中表达是0000 0000 1010 0101 ，
取反是1111 1111 0101 1010，
那么右移5位是0000 0111 1111 1010，
由于是unsigned char型的只能表示低8位的数值，即250
2.
(x&y)+((x^y)>>1)，效果就是求x与y的平均值
把x和y里对应的每一位（指二进制位）都分成三类，每一类分别计算平均值，最后汇总。
其中 一类是x,y中对应位 都是1， 用x&y计算其平均值；
一类是x,y中对应位 有且只有一位是1，用(x^y)>>1计算其平均值；
一类是x,y中对应位 均为0， 无须计算。
第一部分：
x,y对应位均为1，相加后再除以2还是原来的数，如两个00001111相加后除以2仍得00001111。
第二部分：
对应位有且只有一位为1，用“异或”运算提取出来，然后>>1(右移一位，相当于除以2）。
第三部分：
对应位均为零，因为相加后再除以二还是0，所以不用计算。
三部分汇总之后就是(x&y)+((x^y)>>1)
这样可以避免溢出：
假设x,y均为unsigned char型数据(0~255，占用一字节)，显然，x,y的平均数也在0~255之间，但如果直接x+y可能会使结果大于255，这就产生溢出，虽然最终结果在255之内，但过程中需要额外处理溢出的那一位，在汇编中就需要考虑这种高位溢出的情况，如果(x&y)+((x^y)>>1)计算则不会。
3.
利用 位运算 实现两个整数的 加法运算
！！！！！！重点： 异或 常被认作不进位的加法运算
#include <stdio.h>
int main(void) {
int add(int a,int b);
int m,a,b;
scanf("%d,%d",&a,&b);
m = add(a,b);
printf("m=%d",m);
return 0;
}
int add(int a,int b){
if(b == 0) return a;//没有进位时，完成运算，a为最终和。
int sum,carry;
sum = a ^ b;//没有进位的加法运算
carry = (a & b) << 1;//进位，左移运算。
return add(sum , carry);//递归，相加。
}
注释：
* x ^ y ：实现不进位的加法，那么我们接下来就要将进位的数据加上，就可以实现了。
* x & y : 这个操作，即是找出相同位，为什么我们需要找出相同的位呢，因为只 1 & 1 ，这种情况才会 产生进位，可能有人会想那 0 & 0 呢，这个没有影响的。
* (x & y) << 1：为什么要左移呢，其实也很简单，即然后我们都已经找出需要进位的位，那么说明在该位置的前面一位，应该加上1，所以应该左移1位，就是加上余数
4.
有两个变量a和b，不用“if”、“?:”、“switch”或其他判断语句，找出两个数中间比较大的。
第一种:
int max = ((a+b)+abs(a-b))/2;
abs是取绝对值。
如果a>b，那么a-b>0，所以表达式就变成了(a+b+a-b)/2=(a+a)/2=a。
如果a<b，那么a-b<0，取绝对值变成-(a-b)，所以表达式变成了(a+b-a+b)/2=(b+b)/2=b。
第二种：
int c = a-b;
char *strs[2] = {"a large","b large"};
c = unsigned(c)>>(sizeof(int)*8-1);//判断符号位
注释：
sizeof(int) 字节数
sizeof(int)*8 位数
右移sizeof(int)*8 - 1 符号位
该语句的目的是求出c的最高位的值，
当该值为1时，表示c为负数，因此判断出a小于b。
当该值为0时，表示c为零或者整数，因此判断出a大于等于b
5.
给三个整数a、b、c，函数实现取三个数的中间数，不可以使用sort，整数操作尽可能少。
（思路：输入的三个值 中值就是第二大的数值
选中两个进行比较 找到较大的
较大的与第三个值比较
1.如果较大的 < 第三个值 那这个较大的 就是第二大的数值 就是中值
2.较大的 > 第三个值 比较第三个值与 较小的值
1.第三个值 > 较小的值 第三个值 是中值
2.第三个值 < 较小的值 较小的值 是中值）
注意等于号
int median( int a, int b, int c )
{
int min,max;
if ( a < b )
{
min = a;
max = b;
}
else
{
min = b;
max = a;
}
// 此时有 min<=max
if ( max <= c )
return max;
else // min <= max, c <max,
{
// 比较min和c
if ( min <= c ) // min <=c < max
return c;
else
return min; // c< min <= max
}
}
6.
如何将a、b的值进行交换，并且不使用任何中间变量？
（单纯的加减交换会有溢出的可能 尽量用异或）
void swap(int& a, int& b) //使用位运算也可以交换两个值
{
a = a^b;
b = a^b;
a = a^b;
}
7.
评价一下C与C++的各自特点。如果一个程序既需要大量运算，又要有一个好的用户界面，还需要与其他软件大量交流，应该怎样选择合适的语言？
因为C++是面向对象的，在封装、继承、多态这些特性上，会有比较大的开销，所以单从运行效率而言，C更适合一些。
但是和C++相比，C的图形库相对而言种类比较少，而且比较简单，所以在比较复杂的界面设计上，C++会更有优势。因此到底用C还是C++并没有并且的答案，如果目标平台的硬件性能比较弱，并且GUI界面比较简单，推荐用C，反之推荐C++。