概述在计算机程序中所有的数都是以二进制形式存储的。位运算就是直接对整数在二进制进行计算操作。作为一名程序员掌握位运算的基本使用是很重要的,而对于算法程序员来说,位运算的灵活使用能够更灵活高效的解决很多问题。 位运算都有哪些
运算符逻辑按为与(&)参加运算的两个数按二进制进行与运算。 0&0=0 用途: 清零 任何数与0做与运算结果都为0。 取指定位 比如要取一个数的低4位,则只需使用该数与(0000 1111)做与运行,结果就是这个数的低4位的值。 奇偶判断 只要二进制的末尾为0则是偶数,为1则为奇数。因此可用 按位或(|)参加运算的两个数按二进制进行或运算。
用途: 将某位设置为1 如X=0101,需要将第2位设置为1,结果变为0111,则只需和(0010)进行或运算,0101|0010=0111。 按位异或(^)参加运算的两个数按二进制进行异或运算。 0^0=0 用途: 翻转指定位 如要将X=0101 1010的低4位翻转为0101,则只需和Y=0000 1111进行异或运行,X^Y=0101 0101 。 交换两数值 如X=0101,Y=0100,需要将X和Y的值进行交换。
按位取反(~)参加运算的1个数据各位值0变1,1变0. ~0101=1010 用途: 取反运算和用于快速获得某个特定值,如获取一个最低位为0其他位为1的数,则对1进行取反即可,~1。 左移运算符(<<)参与运算的1个数据各位左移,高位丢弃,低位补0。
如果左移的数最高位不等于1,则相当于乘2。 右移运算符(>>)参与运算的1个数据各位右移,如果该数为正则高位补0,反之补1,低位丢弃。 0101 >> 1 = 0010 某数进行右移运算相当于除以2。 无符号右移运算符(>>>)又称逻辑右移,不管正负,高位补0。
如负数 11111111111111111111111111111011>>>1=01111111111111111111111111111101 注:负数的二进制表示形式为补码。 有哪些骚操作技巧一
应用:检测整数x是否是2的次幂 思路:2的次幂满足以下条件:
则x & (x - 1)的结果如果等于0则表示x是2的次幂。 技巧二
一个数据集合中,只有1个数字出现1次,其他数字都出现两次,找出这个数。 思路:只需要将所有数据进行异或运算,结果就是这个数。 一个数据集合中,只有2个数字出现过1次,其他数字都出现过两次,找出这两个数。 思路:假设这两个数是X,Y,所有数字进行异或的结果就是X^Y,因为异或运算逻辑是相同为0,不同为1,则找出这个结果的二进制中等于1的位置,然后将所有数字按照该位是否为1分成两部分,那么X和Y会被分开,然后分别做异或运算,结果便是X和Y. 小结位运算在各大互联网公司的面经中经常会出现,各种算法题中也高频使用,希望本文能让你对位运算有一个初步的认识。 来都来了,点个赞再走啦~ |
|
来自: 520jefferson > 《数据结构与算法》