来自 技术 2019-03-16 的文章

位操作的个人总结 - 红城客栈蓝精灵

在计算机中所有数据都是以二进制形式进行存储,而位运算就是直接对内存中的二进制数据进行操作,因此处理速度非常快。

1. 基本操作

运算符用法示例运算规则按位与 ANDa & b只有两个操作数相应的比特位都为1时,结果才为1,否则为0按位或 ORa | b只有两个操作数相应的比特位都为0时,结果才为0,否则为1按位异或 XORa ^ b两个操作数相应比特位不相同时,结果为1,否则为0按位取反 NOT~a操作数相应比特位取反,0变为1, 1变为0左移a << b将a的二进制形式向左移b个bit,右侧填充0右移a >> b将a的二进制形式向右移b个bit,有符号数逻辑移位,无符号数算术移位

C/C++中移位运算包含逻辑移位(Logical shift)和算术移位(Arithmetic shift)两种,其中逻辑移位的意思是,移出去的位直接舍弃,空缺位用0填充;算术移位的意思是,移出去的位直接舍弃,空缺位用符号位填充。

对于无符号数,无论是左移还是右移都是逻辑移位,如0011 0110 左移两位结果为1101 1000,右移两位结果为0000 1101。对于有符号数,左移仍然是逻辑移位,右移则略有不同,进行的是算术移位,如1011 0110 左移两位结果为1101 1000,右移两位结果为1110 1101(前面两位填充的是符号位1)。

2. 常见应用

对n的指定位进行操作,其它位保持不变。

1 n &= ~(1 << 5); // 1左移5位得到 0010 0000, 按位取反得 1101 1111,与n按位与使其第6位被清零,其它位不变2 n |= (1 << 5); // 1左移5位得到 0010 0000, 与n按位或使其第6位被置1,其它位不变3 n ^= (1 << 5); // 将n第6位取反,其它位不变

判断给定正整数n的奇偶

1 1 bool flag = a & 1; // a对应二进制数末位为0则为偶数,否则为奇数。相比 bool flag = (a % 2 == 0); 运算速度快了很多。

判断n是否为2的正整数次幂

1 /*===============================================================================================2 * 将2的次幂写成二进制容易发现,二进制中只有一个1,后面跟了n个0。3 * 如果将这个数减1,仅有的一个1变成了0,后面的n个0变成了1。时间复杂度O(1)。4 *=============================================================================================== */5 bool isPowerOfTwo(int n) {6 return (n & (n - 1) == 0); 7 }

1 /*============================================================================================== 2 * 常规思路:利用循环判断n是否能被2整除,如果是除以2,继续循环。 3 * 最终结果若为1则表明其是2的正整数次幂,否则不是。时间复杂度O(log n)。 4 *============================================================================================== 5 */ 6 bool isPowerOfTwo(int n) { 7 while (n % 2 ==0) { 8 n /= 2; 9 }10 return (n == 1); 11 }

统计给定正整数的二进制中1的个数

1 /*============================================================================================== 2 * 与上述判断n是否为2的正整数次幂时相似,n&(n -1) 作用是将n的二进制中最右边的1置为0,如此循环以统计n中1的个数 3 *============================================================================================== 4 */ 5 int count1Bit(int n) { 6 int countOneBit = 0; 7 while (n) { 8 countOneBit ++; 9 n &= n -1;        10 }11 return countOneBit;12 }

1 /*============================================================================================== 2 * 另一种四步分组法,以34520(1000011011011000)为例 3 * 第一步:每2位为一组,组内高低位相加。 4 * 10 00 01 10 11 01 10 00 -> 01 00 01 01 10 01 01 00 5 * (10高位为1,低位为0,相加得01;11高位为1,低位也为1,相加得10……)。 6 * 第二步:将第一步得到的结果每4位分为一组,组内高低位相加。 7 * 0100 0101 1001 0100 -> 0001 0010 0011 0001 8 * (0100高位为01低位为00,相加得01;1001高位为10低位为01,相加得11……)。 9 * 第三步:将第二步得到的结果每8位分为一组,组内高低位相加。10 * 00010010 00110001 -> 00000011 00000100。11 * 第四步:将第三步得到的结果每16位分为一组,组内高低位相加。12 * 0000001100000100 -> 00000111。13 * 这样最后得到的结果7即为给定整数中1的个数。14 *==============================================================================================15 */16 int count1Bit(int n) {17 n = ((n & 0xAAAA) >> 1) + (n & 0x5555);                     18 n = ((n & 0xCCCC) >> 2) + (n & 0x3333);                      19 n = ((n & 0xF0F0) >> 4) + (n & 0x0F0F);                      20 n = ((n & 0xFF00) >> 8) + (n & 0x00FF);                    21 return n;22 }

不需要额外变量交换两个整数的值

1 void Swap(int &m, int &n) {2 if ( m != n ) {3 m ^= n; // m = (m ^ n)4 n ^= m; // n = n ^ (m ^ n) = n ^ m ^ n = n ^ n ^ m =m, 一个数和自身异或结果为0,一个数和0异或结果为其自身5 m ^= n; // m = m ^ n = m ^ n ^ m = n6 }7 }

1 void Swap(int &m, int &n) {2 if ( m != n ) {3 int temp = a; // 常规思路:借由中间变量实现交换。4 a = b;5 b = temp;6 }7 }

16位无符号整型数高低位交换

1 /*=========================================================================================2 * 对于16位无符号整型数据,分为高8位和低8位,高八位右移时高位填充0,低八位左移时末位填充0,将两者相加即可。3 *=========================================================================================4 */5 unsigned int lowHighExchange(unsigned int n) {6 return ((a >> 8) + (a << 8)); 7 }

二进制逆序操作

1 /*======================================================================================== 2 * 通过四步分组法得到16位整型数据的二进制逆序。以34520(1000 0110 1101 1000)为例, 3 * 第一步:每2位为一组,组内高低位交换。 4 * 10 00 01 10 11 01 10 00->01 00 10 01 11 10 01 00。 5 * 第二步:每4位为一组,组内高低位交换。0100 1001 1110 0100 -> 0001 0110 1011 0001。 6 * 第三步:每8位为一组,组内高低位交换。00010110 10110001 -> 01100001 00011011。 7 * 第四步:每16位为一组,组内高低位交换。0110000100011011 -> 00011011 01100001。 8 * 改进:对第一步先分别取原数据的奇数位和偶数位 9 * 空位以下划线表示:1_0_0_1_1_0_1_0_, _0_0_1_0_1_1_0_0, 10 * 将下划线填充0得原数 1000 0110 1101 100011 * 奇数位 1000 0010 1000 1000, 偶数位 0000 0100 0101 000012 * 再将奇数位右移一位,偶数位左移一位,将移位后的两数按位或可使奇偶位数据交换。13 * 原数 1000 0110 1101 1000, 奇数位右移一位 0100 0001 0100 010014 * 偶数位左移一位 0000 1000 1010 0000,按位或得 0100 1001 1110 011115 *=======================================================================================16 */17 int binaryReverse( int n ) {18 n = ((n & 0xAAAA) >> 1) | ((a & 0x5555) << 1);                              19 n = ((n & 0xCCCC) >> 2) | ((a & 0x3333) << 2);                             20 n = ((n & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);21 return (((n & 0xFF00) >> 8) | ((a & 0x00FF) << 8));22 }

3. 拓展应用

题目:不使用加减乘除四则运算实现两个正整数相加。

解析:首先理解十进制加法工作原理,主要分为三步,以4+9为例:1)相加相应位的值,不算进位,得3;2)计算进位值,得10,如果进位值为0则第一步得到的就是最终结果;3)把前两步的结果相加,重复此过程得结果13。

再来看二进制相加过程。1)相加相应位的值,不算进位,100 + 1001,得1101;2)计算进位值,得0000,如果进位为0则第一步得到的就是最终结果;3)把前两步的结果相加,重复此过程的结果1101。

1 /*==================================================================================================2 * 相加相应位的值可按位异或,因为如果不考虑进位的和,只有0+1或者1+0才是1, 刚好符合异或的性质:0100 ^ 1001 = 11013 * 计算进位可使用按位与,因为只有1+1才会发生进位并需要将这个进位左移1位: (0100 & 1001) << 1 = 00004 * 然后一直循环直到进位为0,此时的结果就是输入两数之和了。5 *==================================================================================================6 */7 int Add(int num1, int num2) {8 return num2 ? Add(num1 ^ num2, (num1 & num2)<<1) : num1; }

题目:给定一个非空整数数组,其中有一个元素只出现一次,其它元素均出现两次,请找出只出现一次的元素。(要求实现算法具有线性时间复杂度,并且不实用额外空间)

示例:输入[2, 2, 1],输出1。输入[3, 1, 2, 3, 1],输出2。

解析:由于要求时间复杂度O(n),空间复杂度O(1),不能用排序,也不能使用map。考虑使用位操作运算求解。因为任何数与自身异或结果为0,任何数与0异或结果为其自身,将所有元素做异或运算,即a[1]⊕a[2]⊕...⊕a[n],那么结果就是只出现一次的元素,时间复杂度O(n)。过程如下图:

题目:给定一个非空整数数组,其中有两个元素只出现一次,其它元素均出现两次,请找出只出现一次的两个元素。(要求实现算法具有线性时间复杂度,而且只能开辟固定大小的内存空间,即与n无关)

示例:输入[1, 2, 2, 1, 3, 4],输出[3, 4]。

解析:根据前面找一个不同数的思路,如果这里再把所有元素异或,得到的结果是只出现一次的两个元素异或得到的值。然后由于这两个只出现一次的元素一定不相同,那么这两个元素的二进制形式肯定至少有一位不同,即1个为0,另一个为1,先在需要找出这一位。根据异或的性质:任何数与自身异或结果为0,得到这个数字二进制形式中任意一个为1的位都是我们要找的。之后以这一位是0还是1为标准,将数组的n个元素分成两部分。将这一位为0的所有元素异或得到的结果就是只出现一次的两个元素中的一个。将这一位为1的所有元素异或得到的结果就是只出现一次的两个元素中的另一个。如果忽略寻找不同位的过程,公遍历数组两次,时间复杂度O(n)。过程如下图:


Reference:

[1]https://www.cnblogs.com/zhoug2020/p/4978822.html

[2]https://blog.csdn.net/qq_16137569/article/details/82790378

[3]https://www.cnblogs.com/thrillerz/p/4530108.html

[4]https://www.cnblogs.com/fivestudy/p/10275446.html

[5]https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

标签:   电子商务建站      指纹解锁封装   
上一篇:oracle 12c 多租户体系结构概念之数据字典、服务、
下一篇:没有了