点击上方蓝字设为星标
每周一、三、五上午 8:30 准时推送
下面开始今天的学习～
计算机中的数在内存中都是以二进制形式进行存储的，用位操作就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。位操作是各大互联网公司面试经常会问的一类问题。
位操作符
& 与运算 两个位都是 1 时，结果才为 1，否则为 0，如
  1 0 0 1 1 
&  1 1 0 0 1 ------------------------------ 
  1 0 0 0 1 
| 或运算 两个位都是 0 时，结果才为 0，否则为 1，如
  1 0 0 1 1 
|   1 1 0 0 1 ------------------------------ 
  1 1 0 1 1 
^ 异或运算，两个位相同则为 0，不同则为 1，如
  1 0 0 1 1 
^  1 1 0 0 1 ----------------------------- 
  0 1 0 1 0 
~ 取反运算，0 则变为 1，1 则变为 0，如
~   1 0 0 1 1 ----------------------------- 
   0 1 1 0 0 
<< 左移运算，向左进行移位操作，高位丢弃，低位补 0，如
int a = 8;
a << 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000
>> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如
unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前：1111 1111 1111 1111 1111 1111 1111 1000
移位前：1111 1111 1111 1111 1111 1111 1111 1111
常见位运算问题
1. 位操作实现乘除法
数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4
2. 位操作交货两数
位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高
//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}
//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}
位与操作解释：第一步：a ^= b ---> a = (a^b); 
第二步：b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a
第三步：a ^= b ---> a = (a^b)^a = (a^a)^b = b
3. 位操作判断奇偶数
只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。
if(0 == (a & 1)) {
 //偶数
}
4. 位操作交换符号
交换符号将正数变成负数，负数变成正数
int reversal(int a) {
  return ~a + 1;
}
整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数
5. 位操作求绝对值
整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位(整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff)，然后根据符号进行相应的操作
int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}
上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)
int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}
6. 位操作进行高低位交换
给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换，求出交换后的值，如：
34520的二进制表示：
10000110 11011000
将其高8位与低8位进行交换，得到一个新的二进制数：
11011000 10000110
其十进制为55430
从上面移位操作我们可以知道，只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位，高位补 0；将 a<<8 即可将 低 8 位移到高 8 位，低 8 位补 0，然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
7. 位操作进行二进制逆序
将无符号数的二进制表示进行逆序，求取逆序后的结果，如
数34520的二进制表示：
10000110 11011000
逆序后则为：
00011011 01100001
它的十进制为7009
在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。
第一步:以每 2 位为一组，组内进行高低位交换
交换前： 10 00 01 10 11 01 10 00
交换后： 01 00 10 01 11 10 01 00
第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换
交换前： 0100 1001 1110 0100
交换后： 0001 0110 1011 0001
第三步：以每 8 位为一组，组内高低位进行交换
交换前： 00010110 10110001
交换后： 01100001 00011011
第四步：以每16位为一组，组内高低位进行交换
交换前： 0110000100011011
交换后： 0001101101100001
对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：
原数：  10000110 11011000
奇数位： 10000010 10001000
偶数位： 00000100 01010000
再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：
原数：  10000110 11011000
奇数位右移一位： 0 10000010 1000100
偶数位左移一位：0000100 01010000 0
两数相或得到： 01001001 11100100
上面的方法用位操作可以表示为：
取a的奇数位并用 0 进行填充可以表示为：a & 0xAAAA
取a的偶数为并用 0 进行填充可以表示为：a & 0x5555 因此，上面的第一步可以表示为：
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理，可以得到其第二、三和四步为：
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为：
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
8. 位操作统计二进制中 1 的个数
统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：
第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
第二次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}  
本文作者：Shawn
编辑&版式：霍霍
声明：本文归 “力扣” 版权所有，如需转载请联系。

	

一般判断奇偶数是用 num % 2 == 0 来判断，如果为true则为偶数，为false则为奇数。
偶数在二进制里面，最后一位为0，奇数则为1。所以可以通过与1做位与运算判断奇偶数。(num & 1) == 0 如果结果为true则为偶数，为false则为奇数。效率比取余运算高的多。

概要
有过开发经验的童鞋可能已经注意到，很多时候在Java标准库的源码中可以看到位运算的身影，本质原因是位运算能提高算法效率。在之前发布的博文中曾提到过原因LeetCode进阶-彩蛋一，也有一些实际运用的例子，比如按位与&判断奇偶数LeetCode进阶-1025（动态规划)，移位<<(>>)和&结合存储数据存取LeetCode进阶-1029（贪心）。本篇将结束位运算中的异或运算^的巧妙用法。
原题
136. Single Number （Easy)
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1] Output: 1 Example 2:
Input: [4,1,2,1,2] Output: 4
tag: Bit Manipulation
136. 只出现一次的数字 (简单）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1 示例 2:
输入: [4,1,2,1,2] 输出: 4
分类：位运算
题意分析&&思路设计
根据题意，需要找出数组中唯一的没有重复出现的整数。由于本篇是位运算实践科普篇，在分析之前先来看下^异或运算符的特性：第一个操作数的的第n位于第二个操作数的第n位 相反，那么结果的第n为也为1，否则为0。简单来说^运算有两个比较典型的应用特性：1、相同数字（整数）进行^运算结果为0。假设a=b,由于a和b每一位上的数字相同，因此最终a^b=0，结合本题。2、任何数字（整数）异或0，即n^0=n，同理可得。除了一个数字只出现了一次，其他任何数都出现两次。也就是[a,a,b,b,c,c...x,d,d,e,e..]（列举示例，实际顺序忽略）中找出只出现一次的x。显然依次将所有数字进行^运算，利用相同数字n^n=0,x^0=x特点最后计算结果必然为只出现了一次的整数。
编码实践
	public int singleNumber(int[] nums) {
		int res = 0;
		int len = nums.length;
		for (int i = 0; i < len; i++) {
			res ^= nums[i];
		}
		return res;
	}
结语
本题属于位运算科普篇，属于位运算的基本技巧。最后，如果觉得本文对你有所帮助或启发那就来个赞吧0.0～

目录

位运算基础

按位与（&）

按位或（|）

按位非（~）

按位异或（^）

有符号左移（<<）

有符号右移（>>）

无符号右移（>>>）

其他应用实例（待补充）

n&(n-1)

判断一个数是否为2的幂

求数中某一个数的二进制表示中1的个数

位运算执行效率更高比一般的数值运算效率更高。

位运算基础

按位与（&）

只有两个数的值为1时，返回1；其余返回0

应用：判断奇偶性

用数n和1进行按位&，速度比n%2快，即n&1

原理：奇数的二进制码最后一位一定为1，而1只有最后一位1，按位&之后，奇数&1结果为1，偶数&1结果为0.

按位或（|）

只要两个数中有一个数为1，返回1；其余返回0

应用：求整

浮点数n与0进行|运算，即n|1

原理：浮点数不支持位运算，先会被转化为整数再进行位运算

按位非（~）

求二进制的反码

有符号的32位二进制的最高位代表正负，1代表负数，0代表整数。

应用

十进制转换为二进制：（例如-2）

11111111111111111111111111111110 //最高位为1，是负数

10000000000000000000000000000001 //最高位不变，其余位取反

10000000000000000000000000000010 //加1，得到十进制为-2

二进制转换为十进制：（例如-5）

00000000000000000000000000000101 //5的二进制

11111111111111111111111111111010 //取反

11111111111111111111111111111011 //加1

按位异或（^）

两个数中只有一个1时返回1，其他情况返回0

应用：调换两个数字的值

var num1 = 1, num2 = 2;

num1 ^= num2; // num1 = num1 ^ num2 = 1 ^ 2 = 3

num2 ^= num1; // num2 = num2 ^ (num1 ^ num2) = 2 ^ (1 ^ 2) = 1

num1 ^= num2; // num1 = num1 ^ num2 = 3 ^ 1 = 2

console.log(num1); // 2

console.log(num2); // 1

原理：数字与数字本身异或按位异或操作得到的是0

有符号左移（<<）

将二进制除了符号位的所有位向左移动指定位数，右侧补0

应用：求2的n次方

1<<n

有符号右移（>>）

将二进制除了符号位的所有位向右移动指定位数，右侧补0

求一个数的1/2：n>>1

无符号右移（>>>）

正数的无符号右移和其有符号右移结果一样，负数的无符号右移会移动符号位，而且无符号右移会把负数的二进制码当成正数的二进制码。

var num = -64; // 11111111111111111111111111000000

num = num >>> 5; // 134217726

应用：判断数的正负

n>>>0

原理：未移动位数，但负数的右移会将其变为正数。

-1>>>0 4294967295

console.log(-1>>>0); //4294967295

其他应用实例（待补充）

n&(n-1)

作用：将n的二进制表示中的最低位1改为0

如：n=10100 n-1 = 10011 n&(n-1)=10000

判断一个数是否为2的幂

n > 0 && ((n & (n - 1)) == 0 )

2的幂：二进制表示中只有一个1

如n = 1000 n-1 = 0111 则n&(n-1) = 0

求数中某一个数的二进制表示中1的个数

while (n >0 ) {

      count ++;

      n &= (n-1);

}

 

未完待续...