- 说明：
（1）位运算符中除 ~ 外，均为二目运算符，即要求出侧各有一个运算量。
（2）运算早只能是整型或字符型的数据，不能为实型数据。 - 使用位移运算可以提高因乘除运算带来的效率的问题，它的缺点是存在精度损失且不直观。
- 使用移位运算来避免乘法运算是一种常用技巧，不过乘数必须都是正整数，而且必须至少有一个是 2 的 n 次方，例如：2，4，8，16，32……移位运算的特点是速度快，而乘法运算速度较慢，把乘法运算转化为移位运算可以稍微提高程序运行效率。
- 例题1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
12 * 2 = 12 << 1
12 * 4 = 12 << 2
12 * 8 = 12 << 3
12 * 16 = 12 << 4
12 * 32 = 12 << 5
12 * 64 = 12 << 6
12 * 128 = 12 << 7
12 * 256 = 12 << 8
//除法
12 / 2 = 12 >> 1
12 / 4 = 12 >> 2
12 / 8 = 12 >> 3
12 / 16 = 12 >> 4
12 / 32 = 12 >> 5
12 / 64 = 12 >> 6
12 / 128 = 12 >> 7
12 / 256 = 12 >> 8
//其它
num *= 32;
//等同于
num <<= 5;
/* 2 的 5 次方等于 32 */
//如果乘数不是 2 的 n 次方，我们可以把乘数分解成几个 2 的 n 次方的和：
num *= 20;
//等于
num *= (16 + 4);
//等于
num = num * 16 + num * 4;
//等于
num = (num << 4) + (num << 2);
二进制
- 原码:指一个二进制数左边加上符号位后所得到的码，且当二进制数大于0时，符号位为0；二进制数小于0时，符号位为1；二进制数等于0时，符号位可以为0或1
- 反码：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。
- 补码：正数的补码与原码相同，负数的补码是其对应正数二进制所有位取反后加1。
- 在计算机中通常使用补码进行储存。
- 二进制的最末位为0表示该数是偶数，最末位为1表示该数为奇数
位运算
“~”运算
又称取反运算，就是对一个二进制数按位取反。
对于 int 来说，~x = −x−1
“&”运算
- “&”运算，即“and” 运算，也是一种逻辑运算符，对于二进制运算来说，“&”运算的意义是对于两个二进制数的每一位，除了11得1，其他均为0
- 可以用 & 运算判断一个数是奇数还是偶数，当 x 为奇数时， x 二进制下的第 0 位一定是 1 ，否则为 0 。我们让
x & 1，就可以知道 x 的奇偶性了。- &运算通常用于二进制取位操作，例如一个数 &1的结果就是取二进制的最末位。所以可以用来判断奇偶性
- 举个栗子：
10101(21) & 11100(28) = 10100{20}
-
如果参加 & 是负数（
-3 & -5），则以补码形式表示为二进制数。然后按位进行 与 运算。 -
x & (x - 1)用于消去x二进制最后一位的11
2
3x = 1100 00|0100|1100
x - 1 = 1011 00|0100|1011
x & (x - 1) = 1000 00|0100|1000
“|” 运算
- 即 “or” 运算，也是一种逻辑运算符，对于二进制运算来说，“|” 运算的意义是对于两个二进制数的每一位，除了00得0，其它都是1
- 举个栗子：
10101(21) | 11100(28) = 11101(29)
- 举个栗子：
- 通过与运算和或运算的栗子可以观察到一下规律：
x & y<=x和x | y>=x
“^”运算
- “^”运算，又称“xor”运算，异或运算。定义是对于两个二进制数的每一位，相同为0，不同为1
- 举个栗子：
10101(21) ^ 11100(28) = 1001(9)
- 举个栗子：
- 对于一个形如2∗n 的数 x，
x ^ 1=x+1,而对于一个形如 2∗n+1的数x，x ^ 1=x−1 - 异或运算的妙用：
- 0^0=0,0^1=1 可理解为：0异或任何数，其结果=任何数
- 1^0=1,1^1=0 可理解为： 1异或任何数，其结果=任何数取反
- 任何数异或自己，等于把自己置0
- 异或运算符的特点是：数a两次异或同一个数b（a=a^b^b）仍然为原值a.
- 如果 x ^ y=z 那么 y ^ z=x， x ^ z=y
- a xor c == b xor c 则 a == b
- a ^ b = b ^ a
- a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
- d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
- a ^ b ^ a = b.
- (a xor b） xor b = a;
- 由于xor满足交换律，所以上述特性这样表述也是对的：
- 不借助中间变量，交换两个数有以下方法👇
-
1. 相互加减
1
2
3
4
5
6
7a = a + b; //但是加法可能导致溢出
b = a - b; //x和y同号的情况下容易溢出
a = a - b;
x=x-y; //x和y异号的情况下容易溢出
y=x+y;
x=y-x; -
2.异或运算
1
2
3
4
5a = a^b;
b = a^b;
a = a^b;
//可简写为如下
b ^= a ^= b ^= a; -
这东西理论上能比正常的交换优一点，当然还是用 swap 吧，毕竟人家什么都能换，这个只能换整数。
找出2n+1个数中不成对的数
- 给出n个数，其中有且仅有一个出现了奇数次，其余的都出现了偶数次。用线性时间常数空间找出这个出现奇数次的数原
-
lowbit运算
快速判断奇偶性
- 上面有
在状压情况下的操作
快速幂
位运算的优先级
- 位运算的优先级，大致按下面排序
- 加减运算 > 移位运算 > 比较大小运算 > 与运算 > 异或运算 > 或运算
近期评论