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

前言

    首先,我们要了解一个概念:程序中的所有数在计算机内存中都是以二进制的形式储存的。而位运算,就是直接对在内存中的二进制位进行操作,跳过了 程序转义成二进制的这一步骤,对编译时间有所提高,但带来的缺点也很明显,程序的可读性变低了。
    掌握位运算 是一位程序员的基本素养,位运算在计算机领域的作用可谓举足轻重。
    下面我将讲解 位运算的大体方法以及一些基本的应用。

正文

and 运算

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

& 1

判断 n的第m位数

介绍两个重要应用,来证明其含义:

  1. (n >>m ) & 1
    判断 整数n 的二进制 第m位 是否 为1 或者 为0
    n 的第m位数,如果为1 ,1&1 就返回1 ,如果为0,0&1 就返回0
  2. 判断 奇偶性
    如果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. 1 << m
    定位到 n的第m位数

  2. ~(1 << m)
    将1进行非运算,变为 0,其他剩下的m位,变成 1,而 &1,是无实际作用的

  3. n & 0 :& 按位与运算
    只有对应的两个数 全部为1时,结果才为1,而&0,返回值一定为 0

or运算

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

| 1

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

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

  1. 1 << m
    定位到 n 的第m位数

  2. 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. 1 << m : 定位到 n的第m位数

  2. 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 运算

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

    实际上,右移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,请勿用于任何商业用途。
深入Web全栈各项技术,坚持原创,文章更新虽不定,但只为质量而生。
建议收藏这个坏掉的番茄 tomotoes.com ,愿陪你一起在全栈的道路上努力前行!