统计整数二进制表示中1的个数
这是一个很有意思的问题，也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight，而且wikipedia上也提供了很好的位运算解决的方法，这个下面也会提到。
解决这个问题的第一想法是一位一位的观察，判断是否为1，是则计数器加一，否则跳到下一位，于是很容易有这样的程序。
int test(int n)
{
int count=0;
while(n != 0){
if(n%2 ==1)
count++;
n /= 2;
}
return count;
}
或者和其等价的位运算版本：
int test(int n)
{
int count=0;
while(n != 0){
count += n&1;
n >>= 1;
}
return count;
}
这样的方法复杂度为二进制的位数，即[tex]\log_2n[/tex]，于是可是想一下，有没有只与二进制中1的位数相关的算法呢。
可以考虑每次找到从最低位开始遇到的第一个1，计数，再把它清零，清零的位运算操作是与一个零，但是在有1的这一位与零的操作要同时不影响未统计过的位数和已经统计过的位数，于是可以有这样一个操作 n&(n-1) ，这个操作对比当前操作位高的位没有影响，对低位则完全清零。拿6（110）来做例子，第一次 110&101=100，这次操作成功的把从低位起第一个1消掉了，同时计数器加1，第二次100&011=000，同理又统计了高位的一个1，此时n已变为0，不需要再继续了，于是110中有2个1。
代码如下：
int test(int n)
{
int count=0;
while(n != 0){
n &= n-1;
count ++;
}
return count;
}
这几个方法虽然也用到了位运算，但是并没有体现其神奇之处，下面这个版本则彰显位运算的强大能力，若不告诉这个函数的功能，一般一眼看上去是想不到这是做什么的，这也是wikipedia上给出的计算hamming_weight方法。
int test(int n)
{
n = (n&0x55555555) + ((n>>1)&0x55555555);
n = (n&0x33333333) + ((n>>2)&0x33333333);
n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
return n;
}
没有循环，5个位运算语句，一次搞定。
比如这个例子，143的二进制表示是10001111，这里只有8位，高位的0怎么进行与的位运算也是0，所以只考虑低位的运算，按照这个算法走一次
+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | <---143
+---+---+---+---+---+---+---+---+
| 0 1 | 0 0 | 1 0 | 1 0 | <---第一次运算后
+-------+-------+-------+-------+
| 0 0 0 1 | 0 1 0 0 | <---第二次运算后
+---------------+---------------+
| 0 0 0 0 0 1 0 1 | <---第三次运算后，得数为5
+-------------------------------+
这里运用了分治的思想，先计算每对相邻的2位中有几个1，再计算每相邻的4位中有几个1，下来8位，16位，32位，因为2^5＝32，所以对于32位的机器，5条位运算语句就够了。
像这里第二行第一个格子中，01就表示前两位有1个1，00表示下来的两位中没有1，其实同理。再下来01+00=0001表示前四位中有1个1，同样的10+10=0100表示低四位中有4个1，最后一步0001+0100=00000101表示整个8位中有5个1。
15身份证号码转18位的程序
以前在哪看到的，安全焦点吧！丢这做个备份
/*输入原来的15位身份证号码，产生新的18位身份证号码的程序*/
#include "stdio.h"
#include "string.h"
#include "conio.h"
/*
* gen New 18 ID Card from old 15 ID
*/
char genNewID( char ID[], char NewID[])
{
int W[18] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1};
char A[11] = {'1','0','x','9','8','7','6','5','4','3','2'};
int i,j,S;
if(strlen(ID) != 15)
return -1;
memcpy( NewID, ID, 6 );
NewID[6]='1';
NewID[7]='9';
NewID[8]=0;
strcat( NewID, &ID[6] );
S = 0;
for(i=0;i<17;i++)
{
j = (NewID[i] - '0') * W[i];
S = S + j;
}
S = S % 11;
NewID[17] = A[S];
NewID[18] = 0;
return A[S];
}
int main(int argc, char* argv[])
{
char ID[20], NewID[20], ret;
puts("输入原来的15位身份证号码，产生新的18位身份证号码\n");
do{
printf("Input your old 15 ID Card: ");
scanf( "%s", ID );
if(stricmp(ID, "exit") == 0)break;
ret = genNewID( ID, NewID );
printf("Your New 18 ID Card: %s \n", ret != -1 ? NewID : "Input Error!!");
}while(1);
getch();
return 0;
}
俄罗斯方块的悲剧
让赛扬机器性能“赶上”四核
今天用 stumbleupon 在网上上乱逛，发现这么个有意思的东西 （这里是原贴）
有人在LKML（linux kernel mailing list）发贴
Hi, all I have two machines that show very different performance numbers. After digging a little I found out that the first machine has, in /proc/cpuinfo: model name : Intel(R) Celeron(R) M processor 1.00GHz while the other has: model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz and that seems to be the main difference. Now the problem is that /proc/cpuinfo is read only. Would it be possible to make /proc/cpuinfo writable so that I could do: echo -n "model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz" > /proc/cpuinfo in the first machine and get a performance similar to the second machine?
这人意思是说他有两个机器，一个赛扬，一个四核，因为/proc/cpuinfo是只读的，能不能让它可写然后他用这个命令
echo -n "model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz" > /proc/cpuinfo
让第一台机器的性能直逼第二台。
很明显这是恶搞，但是有个人很配合的回了句
Good catch! 'chmod +w /proc/cpuinfo' should do the trick.
把/proc/cpuinfo文件权限改下即可。
楼主又来了句
Thanks, that did the trick. My first machine is much faster now and it even has 4 cores! :)
OMG，赛扬比四核还牛B。
呵呵，of course，这是个April Fool's Day 's joke!
Firefox Logo On Google Earth
