几道面试题

请定义一个宏，比较两个数a,b的大小，不能使用大于，小于，if语句

如上面题所述：

答案如下：

#define Max(a,b) (a==b)?e:(((a-b)|1<<31)==(a-b)?b:a)

1<<31   :00000000000001左移31位至最高位    变为1000000000000000000000
而(a-b)可能是正数或者负数或者0，规定：有符号型数据储存在内存中时,最高一位用来储存符号,剩下的位用来储存数据,如果是负数,最高位就是1,如果是正数,最高位就是0
那么：如果(a-b)为负数，则最高位是1 它们按位与的结果是(a-b) 恒等，输出b

#define max(a,b) (((a-b)>>31)|0)?b:a

比较简洁和完全的定义是：

#define Max(a,b) (a==b)?e:((((a-b)>>31)|0)?b:a)

 

求一个INT32整型里面有多少个位是1？

unsigned int countBits(unsigned int x)
{
   const int mask = 1;
   unsigned int result = 0;
   for(short si=0; si<32; ++si)
      result += (x>>si)&mask;
   return result;
}

看看bitwise的函数，如何不用循环来做这个算法。

 代码如下：

Code
unsigned int countBits(unsigned int x)
{
   // count bits of each 2-bit chunk
   x  = x - ((x >> 1) & 0x55555555);
   // count bits of each 4-bit chunk
   x  = (x & 0x33333333) + ((x >> 2) & 0x33333333); 

   // count bits of each 8-bit chunk
   x  = x + (x >> 4);
   // mask out junk
   x &= 0xF0F0F0F;
   // add all four 8-bit chunks
   return (x * 0x01010101) >> 24;
}

如果不是32位整形，而是2位，如何来做这道题。

无非4种组合，写个switch cases就搞定了。。。有没有更好的方法呢，如何通过计算（移位，加，减）得到最后的值。

00 ==》0个1 ==》00

01 ==》1个1 ==》01

10 ==》1个1 ==》01

11 ==》2个1 ==》10

 f(n) = n-(n>>1)&0x01

将32位整形分成2位为一组，则有16组，分别计算出1的个数，其算法是f(n)=n-(n>>1)&0x55555555

这样2位一组的计算完毕，可以看到，结果只有0，1，2。

下面以4位一组，组合的可能如下，这里是做加法：

00 和 00 ==》0个1 ==》0000

00 和 01 ==》1个1 ==》0001

00 和 10 ==》1个1 ==》0010

01 和 00 ==》1个1 ==》0010

01 和 01 ==》2个1 ==》0010

01 和 10 ==》3个1 ==》0011

10 和 00 ==》2个1 ==》0010

10 和 01 ==》3个1 ==》0011

10 和 10 ==》4个1 ==》0100

f(AABB) = AA+BB = (AABB>>2)&0011+AABB&0011

即算法是f(n) = n&0x33333333+(n>>2)&0x33333333

运用同样的方法计算4位一组的结果。f(n)=n&0x0f0f0f0f+(n>>4)&0x0f0f0f0f

最后计算8位一组的结果。f(n) = n&0x00ff00ff+(n>>8)&0x00ff00ff.

最最后计算16位一组的结果。f(n) = n&0x0000ffff + (n>>16)&0x0000ffff，即得到最后的结果。但是上面的代码可不是这样写的。

与0x01010101相乘有一个有趣的结果，如果我们有4个字节A，B，C，D。

A,B,C,D->A+B+C+D,B+C+D,C+D,D

显然，高位字节是我们需要的结果，于是f(n)=(n*0x01010101)>>24

Brian Kernighan and Dennis Ritchie的“The C Programming Language”一书中给出了更好更快的一个算法，不过是用循环做的。

不像其它算法，这个方法的性能很大程度上依赖于输入，当少于4个1时，比其他算法优越得多，都是1时最慢。

countBitsLoop
 1 unsigned int countBitsLoop(unsigned int x)
 2 {
 3    unsigned int result = 0;
 4    // strip one set bit per iteration
 5    while (x != 0)
 6    {
 7       x &= x-1;
 8       result++;
 9    }
10    return result;
11 }

主要的技巧就是x&=x-1：

• 如果 x = 0, 则根本不进 while-loop
• 如果最右一位是1, 则最右一位的x − 1是0. 所有其他位都是一样的x &= x − 1 → x = x − 1.
• 如果最右边的位都是0, 则x看起来是: ...1000. 那么x − 1为: ...0111. x &= x-1的结果是: ...0000.
  总之, x &= x − 1 将所有非点的位清零, 点代表的位不变. 
总的来说，x &= x − 1 将最右边值为1的位变成0.

待添加。。。