Programing - Crane's Blog

Crane

分类

随机文章

标签云

统计整数二进制表示中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;
}

求三个参数中最大两个的平方和

看到一题，实现一个函数，求三个函数中最大的两个参数的平方和。

很自然的，想到这样的方法：

int sum_square_largest(int x, int y, int z){

if(y > x && z > x){
return y * y + z * z;
}

if(x > y && z > y){
return x * x + z * z;
}

if(x > z && y > z){
return x * x + y * y;
}
}

但是可以看到中间的判断都是相似的，由此可就得一更简洁的方法，使用递归。

int sum_square_largest(int x, int y, int z){

if (x <= y && x <= z){
return y * y + z * z;
}

return sum_square_largest(y, z, x);
}

由于这里是尾递归，gcc优化会识别出这个，然后自动调整堆栈，不会出现函数开销在堆栈上花费很多时间资源的情况。

超级快速关机方法

最近不知什么问题,发现有时关机时停在windows正在关机那里时间比较长,而且是偶尔快偶尔慢,吃不准是什么原因,于是就想着有什么好的快速关机的方法。
首先想到的就是那个经典的操作技巧，打开任务管理器，在关机菜单中按住ctrl的同时点关闭，片刻间，机子就关了。
算算这个所费的时间，打开任务管理器（不管是任务栏右键打开还是快捷键），再选菜单，点关闭，得10秒左右吧！
程序员的话就会多想一点，这个玩意用程序怎么实现呢？那个开始菜单关机函数和任务栏的肯定不是一样的，开始菜单的比较优雅一点，提醒保存数据，通知程序退出，然后关机，而任务管理器的就相对粗暴一点，什么也不做，直接就关机，不过速度绝对一流，呵呵，我喜欢，就要这个速度。
查了下资料，一般用的是ExitWindowsEx这个函数，可能也会用InitiateSystemShutdownEx，这里交待下ExitWindowsEx的用法，查MSDN，可以看到函数原型如下：
BOOL ExitWindowsEx(
UINT uFlags, // shutdown operation
DWORD dwReason // shutdown reason
);
其中uFlags有这些选项:
EWX_LOGOFF 注销
EWX_POWEROFF 关闭系统并关闭电源
EWX_REBOOT 关机重启
EWX_SHUTDOWN 关机并指出现在可以安全关机了
还有
EWX_FORCE
EWX_FORCEIFHUNG
强制关机，可能会丢失数据。
dwReason很多，主要这么几个
SHTDN_REASON_MAJOR_APPLICATION Application issue.
SHTDN_REASON_MAJOR_HARDWARE Hardware issue.
SHTDN_REASON_MAJOR_OPERATINGSYSTEM Operating system issue.
SHTDN_REASON_MAJOR_OTHER Other issue.
SHTDN_REASON_MAJOR_POWER Power failure.
SHTDN_REASON_MAJOR_SOFTWARE Software issue.
SHTDN_REASON_MAJOR_SYSTEM System failure.
但这不是这篇文章的重点，这里要说的武器不是公开的，在MSDN中查不到，这是微软的秘密武器，ZwShutdownSystem函数，藏在ntdll.dll中。
利用ZwShutdownSystem(2)关闭电源，这个函数要求有SE_SHUTDOWN_PRIVILEGE权限，因此要先用RtlAdjustPrivilege函数来设置SE_SHUTDOWN_PRIVILEGE，SE_SHUTDOWN_PRIVILEGE的值为0x13,ZwShutdownSystem函数不通知应用程序和服务程序，就直接关闭系统了，关机速度非常快，但是如果有程序没有保存数据的话，是不会有任何提示的。
完整的程序可以这样写：

#include<stdio.h>
#include<windows.h>
#define SE_SHUTDOWN_PRIVILEGE 0x13
int main()
{
int nRet;
int en;
HINSTANCE hs=NULL;
typedef int (*SHUTDOWN)(int);
SHUTDOWN ZwShutdownSystem;
typedef int (*RTL_ADJUST_PRIVILEGE)(int,int,int,int *);
RTL_ADJUST_PRIVILEGE RtlAdjustPrivilege;
hs=LoadLibrary("ntdll.dll");
if(hs==NULL)
{
MessageBox(NULL,"Cannot load DLL file!","error",MB_OK);
}
ZwShutdownSystem=(SHUTDOWN)GetProcAddress(hs,"ZwShutdownSystem");
RtlAdjustPrivilege=(RTL_ADJUST_PRIVILEGE)GetProcAddress(hs,"RtlAdjustPrivilege");
nRet=RtlAdjustPrivilege(SE_SHUTDOWN_PRIVILEGE,TRUE,TRUE,&en);
if(nRet==0x0C000007C)
nRet = RtlAdjustPrivilege(SE_SHUTDOWN_PRIVILEGE,TRUE,FALSE,&en);
nRet=ZwShutdownSystem(2);
FreeLibrary(hs);
return 0;
}

编译运行，一个黑框一闪，机子就关了，像台式机拔电源一样快速。再多想一下，给它创建一个快捷方式，换个图标，然后设置为最小化运行，就看不到黑框了，再加个快捷键，这样的话，按个键，哗一下机子就黑了，光速关机啊！
弱弱的想一下，两个方法是不是本质上是一样的呢？

python的一个彩蛋

统计整数二进制表示中1的个数

15身份证号码转18位的程序

求三个参数中最大两个的平方和

超级快速关机方法