神奇的位运算

位运算在计算机领域的作用可谓举足轻重。

前言

首先，我们要了解一个概念：程序中的所有数在计算机内存中都是以二进制的形式储存的。而位运算，就是直接对在内存中的二进制位进行操作，跳过了程序转义成二进制的这一步骤，对编译时间有所提高，但带来的缺点也很明显，程序的可读性变低了。

掌握位运算是一位程序员的基本素养，位运算在计算机领域的作用可谓举足轻重。

下面我将讲解位运算的大体方法以及一些基本的应用。

正文

and 运算

只有对应的两个二进制数，均为 1，结果才为 1，否则为 0

& 1

判断 n 的第 m 位数。

介绍两个重要应用，来证明其含义：

(n >>m ) & 1 判断整数 n 的二进制第 m 位是否为 1 或者为 0 n 的第 m 位数，如果为 1 ，1&1 就返回 1 ，如果为 0，0&1 就返回 0
判断奇偶性如果 n 为奇数，辗转相除 2，最后的余数必定为 1，如果 n 为偶数，辗转相除余数必定为 0 也就是说，n 为奇数，n&1 等价于 1&1 ，返回 1，n 为偶数，n&1 等价于 0&1，返回 0

& 0

将 n 的第 m 位数，重置为 0 基本应用：n & ~(1 << m)

1 << m 定位到 n 的第 m 位数
~(1 << m) 将 1 进行非运算，变为 0，其他剩下的 m 位，变成 1，而 &1，是无实际作用的
n & 0 ：& 按位与运算只有对应的两个数全部为 1 时，结果才为 1，而&0，返回值一定为 0

or 运算

只有对应的两个二进制数，均为 0，结果才为 0，否则为 1

| 1

将 n 的第 m 位数，重置为 1

基本应用：n | (1 << m):

1 << m
定位到 n 的第 m 位数
n | 1
n 的第 m 位数进行 |1 操作其返回值必定为 1！因为|只有，两个数都为 0 时，结果才为 0

| 0

无实际作用

一定要清楚，是 n 的第 m 位数在进行操作，其他位数操作，根本无影响

因为，其他位数，是在进行 “| 0” 操作，而所谓的 |0 操作，与 &1 操作，毫无差别。

假设 k=n 的第 m 位数，k = 1 ，k|0 = 1|0 = 1，k = 0，k|0 = 0|0 = 0，所谓无实际作用。

但是要注意一点，我说的 0 是在二进制数中的 0，有实际含义的 0，不是补 0 的 0

所以，可以感性的认识到，| 0 与 & 1 以及下文的 ^ 0，都是无实际作用的

xor 运算

只有对应的两个二进制数相等时，结果才为 0，否则为 1

^ 1

将 n 的第 m 位数，取反

基本应用：n ^ (1 << m)

1 << m ：定位到 n 的第 m 位数
n ^ 1，我们要知道，^ (异或）：不相等为 1，相等为 0

而 ^1：如果 n 的第 m 位数为 1，1^1 返回值为 0，如果 n 的第 m 位数为 0，0^1 返回值为 1

所以，^1 的重要作用，就是与之相反的作用

^ 0

无实际作用

假定整数 k 为 0，k^0 = 0^0 = 0 ; 假定整数 k 为 1，k^0 = 1^0 = 1

所以说，无论怎么变化，^0 都是无实际作用的

shl & shr 运算

左移运算符 “<<” 表达式：a << b a<<b 的值是：将 a 各二进位全部左移 b 位后得到的值。左移时，高位丢弃，低位补 0。实际上，左移 1 位，就等于是乘以 2，左移 n 位，就等于是乘以 2n。而左移操作比乘法操作快得多。

例如:9 << 4
9的二进制形式：0000 0000 0000 0000 0000 0000 0000 1001
因此，表达式“9<<4”的值，就是将上面的二进制数左移4位，得：
0000 0000 0000 0000 0000 0000 1001 0000
即为十进制的144 , 而 9*2的4次幂 = 9*16 = 144.

右移运算符 “>>” 表达式：a >> b a>>b 的值是：将 a 各二进位全部右移 b 位后得到的值。右移时，移出最右边的位就被丢弃。对于有符号数，如 long,int,short,char 类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数 C/C++编译器规定，如果原符号位为 1，则右移时高位就补充 1，原符号位为 0，则右移时高位就补充 0。

1 2	实际上，右移 n 位，就相当于左操作数除以2n，并且将结果往小里取整。例如：-25 >> 4 = -2 -2 >> 4 = -1 18 >> 4 = 1

应用

对 2 的整数幂进行模运算

#include <stdio.h>
int main(){
    int n,k;
    while(~scanf("%d %d",&n,&k)){
        n<<=k;//相当于 n 乘以 2 的 k 次幂，并将结果赋给 n 
        
        n>>=k;//相当于 n 除以 2 的 k 次幂，并将结果赋给 n 
        
        printf("%d\n",n);
    }
    return 0; 
}

两数交换

#include <stdio.h> 
int main(){
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        n^=m;
        m^=n;
        n^=m;
        printf("%d %d\n",n,m);
    }
    return 0;
}

按位异或 ^ : 不相同为：1 ; 相同为：0 将参与运算的两操作数各对应的二进制位进行异或操作，即只有对应的两个二进位不相同时，结果的对应二进制位才是 1，否则为 0。

异或运算的特点是：如果 a^b=c，那么就有 c^b = a 以及 c^a=b

例如：表达式“21 ^ 18 ”的值是7(即二进制数111)。
21：    10101
18：    10010
21^18:  00111

假设 n = 5，m = 6 
5的二进制为：101
6的二进制为：110 

n^=m = 5^=6   = 101 ^ 110 = 011 ,
此时 n 的二进制为：011 

m^=n = 6^=011 = 110 ^ 011 = 101 ,
此时 m 的二进制为：101，也正是 5的二进制数，也就是说 m ==开始的 n 

n^=m = 011^=5 = 011 ^ 101 = 110 ,
此时 n 的二进制位：110，也正是 6的二进制数，也就是说 n ==开始的 m

层次结构：A->B B->A A->B 正反正

判断 2 的正整数幂

#include <stdio.h>
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(!(n & (n-1)) && n)
            printf("%d 为 2 的正整数幂\n",n);
        else
            printf("%d 不是 2 的正整数幂\n",n);
    }
    return 0;
}

给定整数 n 判断 n 是否为 2 的正整数幂表达式：(! (n & (n-1)) && n

举个例子： n = 16 = 10000，n-1 = 15 = 1111
那么 ：10000 & 01111 = 00000 = 0 
再举个例子： n = 256 = 10000000 ,n-1 = 255 = 11111111
那么：100000000 & 011111111 = 000000000 = 0

是的，如果一个数 n 是 2 的正整数幂，那么 n 的二进制必定为 1000…. n-1 的二进制必定为 1111…. 即： n & n-1 = 0 所以 (! (n & (n-1)) 为 1 ; && n ：判断 n 为正数

判断奇偶性

#include <stdio.h>
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n&1)
            printf("%d 是奇数\n",n);
        else
            printf("%d 是偶数\n",n);
    }
    return 0; 
}

记住：在做位运算时，位数不够的数，自动在前面补 0 比如：21 & 1 ：10101 & 00001 = 00001 = 1 16 & 1 ：10000 & 00001 = 00000 = 0 事实证明：偶数的二进制的末尾为 0，奇数的二进制的末尾为 1

十进制 m 转换 n 进制方法： m 一直除 n，每相除一次，m 就等于商，直到商为 0，然后余数反排即可。

1的二进制：1/2 =0 余1
余数反排 即是 1的二进制：1 

6的二进制：6/2 =3 余0
          3/2 =1 余1
          1/2 =0 余1 
余数反排 即是 6的二进制：110

15的二进制：15/2=7 余1
           7/2=3 余1
           3/2=1 余1
           1/2=0 余1
余数反排 即是 15的二进制：1111 

5的二进制：5/2 =2 余1
          2/2 =1 余0 
          1/2 =0 余1
余数反排 即是 5的二进制：101

21的二进制：21/2 =10 余1
           10/2 =5 余0
           5/2 =2 余1
           2/2 =1 余0
           1/2 =0 余1
余数反排 即是 21的二进制：10101

其他方面

(n >> m) & 1 == (n >> m) | 0 == (n >> m) ^ 0
n & ~(1 << m) : 将 n 的第 m 位数，重置为 0
n | (1 << m) : 将 n 的第 m 位数，重置为 1
n ^ (1 << m) : 将 n 的第 m 位数，取其相反

结束语

转载本站文章请注明作者和出处 tomotoes.com，请勿用于任何商业用途。

前言

正文