位操作的总结

August 15, 2016

一.什么是位操作

整数在计算机内是以二进制数的形式存储的,所谓的位操作,就是直接对内存中的组成整数的二进制数进行操作。 最基本的位操作有 “与” “或” “异或” “取反” “左移” “右移” 六种

二.基础的位操作

操作 | 运算规则 ---|--- 与 & | 两数同为1时结果为1 或 \| | 两数同为0时结果为0 异或 ^| 两数相同结果为0,不同为1 取反 ~| 0得1 1得0 左移 << |二进制数各位向左移若干位,高位丢弃,低位补0 右移 >> |各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

三.如何使用位操作

1.and操作

and操作可以用来取某一位二进制数,例如二进制数:0110,在与1进行and操作后,就可以取出其最后一位0 and操作可以用于判断奇数偶数,因为二进制数末尾为1时,为奇数;末位为0时,为偶数。

2.or操作

or操作可以对二进制数某一位赋值,比如要将某二进制数最后一位赋值为1,只需将其与1进行or操作,那么如何赋值为0呢?很简单,与1进行or之后减1即可。 这个操作可以用来寻找与一个数最相近的偶数

3.xor操作

xor操作即异或,常用于对某一位进行取反,因为异或操作可以被解释为"是不是相同,相同得0,不同得1" xor的逆运算是它本身,也就是说如果有a,b两个数,(a^b)^b=a,一个数与另一个数进行连续的两次xor操作得到的是它本身,根据这个性质可以进行加密运算,比如 > 我想对我MM说1314520,但怕别人知道,于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500,我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值,得到1314520,于是她就明白了我的企图。 这个例子引用自网络上一篇博文:http://www.matrix67.com/blog/archives/263 接着我们看看xor的另一个用途,用于交换两个int值 在我们之前使用的交换操作中,都需要一个临时变量,那么能不能在不用临时变量的情况下完成交换呢?当然可以。 假如有a,b两个int值,a=1,b=2,对a,b进行下面的运算 ``` a=a^b b=a^b a=a^b ``` 看起来很诡异,其实这个操作的确能起到swap的作用,第一次赋值后a==a^b,第二次操作b被赋值为(a^b)^b,也就是a,第三次操作a赋值为a^(a^b),也就是b,到这里就完成了这个交换的过程而且没有使用临时变量。

4.not运算

not也就是非运算,将二进制数每一位全部取反,使用not运算时要格外小心,你需要注意整数类型有没有符号。如果not的对象是无符号整数(不能表示负数),那么得到的值就是它与该类型上界的差,因为无符号类型的数是用$0000到$FFFF依次表示的。

5.shl操作

a shl b也就是将二进制数每位左移b位,也就是在后面加b个0,实际效果相当于乘以2的b次幂,比如100 shl 2==400。 通常认为a shl 1比a*2更快,因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 – 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂,此时可以用shl来定义Max_N等常量。

6.shr操作

a shr b也就是将二进制数每位右移b位,也就是去掉后b位,效果相当于除以2的b次幂 下面列举的是位操作常见应用,引用自http://www.matrix67.com/blog/archives/263 功能 | 示例 ---|--- 去掉最后一位 | (101101->10110) x shr 1 在最后加一个0 | (101101->1011010) x shl 1 在最后加一个1 | (101101->1011011) x shl 1+1 把最后一位变成1 | (101100->101101) x or 1 把最后一位变成0 | (101101->101100) x or 1-1 最后一位取反 | (101101->101100) x xor 1 把右数第k位变成1 | (101001->101101,k=3) x or (1 shl (k-1)) 把右数第k位变成0 | (101101->101001,k=3) x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) x xor (1 shl (k-1)) 取末三位 | (1101101->101) x and 7 取末k位 | (1101101->1101,k=5) x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) x and (x+1) 把右起第一个0变成1 | (100101111->100111111) x or (x+1) 把右边连续的0变成1 | (11011000->11011111) x or (x-1) 取右边连续的1 | (100101111->1111) (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) x and (x xor (x-1))

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017