位运算处理进制转换问题

位运算处理进制转换问题

一般初学者学习一门语言，一般都有那么经典的几个题，比如判断水仙花，进制转换，计算1加到100的和，输出多少以内的素数或是判断一个数是否是素数等等。我学C语言老师也不厌其烦地布置这类题目，因为我之前有过基础，所以思考题目时总会有些拓展，比如十进制转换成二进制这道题。

老师讲的方法类似于这样

do{
    a[i++]=num%2;}
while((num/=2)!=0);

通过不断的对2取余得到的余数保存在数组a[]里，最后数组里就是得到的二进制数(但是是反的，输出的时候需要从a[n]->a[0]输出)。

这种办法比较好理解，但是从效率上来说还是差了。C语言的魅力就在它有很多对系统底层操作的功能，比如位运算。

一个数在计算机里以二进制保存，我们何不直接把保存在计算机里的二进制数拿出来用呢？后来我写了一个用位运算解决转换问题的程序，网上也有类似的程序，大家也可以去对比对比。

#include<stdio.h>
void main(){
    int n,a[16],i;
    scanf("%d",&n);
    for(i=0;i<16;i++)
        a[i]=(n>>i)&1;
    for(i=15;i>=0;i--) 
        printf("%d",a[i]));
}   

很简单的一段代码，其中第一个for循环作用是将n代表的二进制数一位一位保存在数组a[]中。仔细分析a[i]=(n>>i)&1这个表达式：在计算机里，n已经是一个二进制数了，我们的目的只是把它一位一位分开来。所以n>>i，将n的二进制数向右移i位，相当于第(i+1)位(从右往左数)以右的数据都没了。现在的第1位是移动以前的(i+1)位。再将移动以后的数据和1按位与，因为&的时候1左边自动补0，所以得到的数就是现在的第一位。

举个例子，比如206的二进制数011001110，我想获得它的第4位，也就是1，此时i=3，n>>i 得到000011001，再和1即000000001按位与，得到000000001，也就是1，赋值给a[i]即a[3].

于是这个循环就获得了数n的每一位，不过同样是反的，输出时从a[n]到a[0]输出就可以了。

这个算法理论上比前一个要快很多，因为移位运算远比乘除法运算快。但同样避免不了需要倒置输出的问题，不过我们只需要稍微改动一个，就可以使之顺序变一变。

for(i=15;i>=0;i--)
    a[15-i]=(n>>i)&1;

这个大家可以自己分析一下。通过这样移位，输出时就可以从a[0]到a[i]这样输出了。