位运算

位运算概述

从现代计算机中所有的数据都以二进制的形式存储在设备中。即0、1两种状态，计算机对二进制进行的运算（+、-、*、/）

都叫位运算

位取反(~)

位取反即之前负数转二进制所用的方式，即0变1，1变0。

1
2
10001100
01110011

位与(&)

位与即如果两个位进行比较两位同时为1，结果才为1，否则结果为0。
例如: 125 & 7

1
2
3
4
5
6
7
8
9
10
11
12
13
           125   &    7
 二进制: 01111101 & 00000111
 
位与比较:    
0 1 1 1 1 1 0 1
---------------
0 0 0 0 0 1 1 1
| | | | | | | |
× × × × × √ × √
| | | | | | | |
0 0 0 0 0 1 0 1
 
结果: 125&7 = 0000 0111 = 5

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

  • 利用^ 以及&, 巧妙的进行相加

首先 ,我们有两个数字,

  • 需要先获取 非进位的和 n (n= a^b)
  • 然后获取进位的和 : p (p=a&b<<1)
  • 然后我们 通过 n= n^p 就得到了和 ( 进位和 + 非进位和)

9 : 1001
26: 11010
n: 10011
p: 10000
n: 00011 , 可见, 如果仅仅是 n^p 可能存在新的进位的情况 ,
此时我们继续使用 p 来记录 n&p<<1 的结果 ,
p: 100000
这里需要用到一个新的数字(temp)来储存 n&p<<1 的结果, 因为如果先 异或再 & , 就会导致先相加, 再&, 相当于重复计算了
然后继续执行上一步类似的操作 也就是 n= n^p
n:100011 : 35 得到正确结果

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int add(int a, int b) {
        int n=a;
        int p=b; //存储上一轮的 进位和结果
        while(p!=0){
            int temp = (n&p)<<1;// 存储上一轮的进位和结果  ,如果还有进位那么就继续执行操作
            n=n^p; // 进位和+ 非进位和
            p=temp; //如果还有进位那么就继续执行操作
        }
        return n;
    }
}

位或(|)

位或即如果两个位进行比较两位同时为0，结果才为0，否则结果为1。
例如: 125 | 7

1
2
3
4
5
6
7
8
9
10
11
12
13
           125   |    7
 二进制: 01111101 | 00000111
 
位或比较:    
0 1 1 1 1 1 0 1
---------------
0 0 0 0 0 1 1 1
| | | | | | | |
√ × × × × × × ×
| | | | | | | |
0 1 1 1 1 1 1 1
 
结果: 125|7 = 0111 1111 = 7

异或(^)

位异或即如果两个位进行比较相同取0，不同取1。

x^x=0

例如: 125 ^ 7(java中^代表异或)

1
2
3
4
5
6
7
8
9
10
11
12
13
           125   ^    7
 二进制: 01111101 ^ 00000111
 
位异或比较:    
0 1 1 1 1 1 0 1
---------------
0 0 0 0 0 1 1 1
| | | | | | | |
√ × × × × √ × √
| | | | | | | |
0 1 1 1 1 0 1 0
 
结果: 125^7 = 0111 1010 = 122

异或的几条性质:

  1. 交换律
  2. 结合律 (ab)c == a(bc)
  3. 对于任何数x，都有 xx=0，x0=x
  4. 自反性: a^ b^ b= a ^ 0=a;

编程算法中的作用:交换两个数(利用性质)

1
2
3
4
5
6
7
public void Swap(int  &a,  int  &b){  
  if  (a  !=  b){  
    a  ^=  b; //a=a^b
    b  ^=  a; //b=b^(a^b) = (b^b)^a = a 
    a  ^=  b; //a=(a^b)^a = (a^a)^b = b
        }  
}

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

利用相同的数字异或的结果为0 以及 任何数字异或0都是它本身的性质 ,

将数组中所有的数字 ^ 然后返回即可得到结果

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res=nums[0];
        for(int i=1;i<nums.length;i++){
            res^=nums[i];
        }
        return  res;
    }
}

右移(>>)

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
125>>3

1
2
3
4
5
6
7
8
9
10
11
           125   >>    3
右移:    
0 1 1 1 1 1 0 1
---------------
0 0 1 1 1 1 1 0 |1     >> 1
0 0 0 1 1 1 1 1 |0 1   >> 2
0 0 0 0 1 1 1 1 |1 0 1   >> 3
^ ^ ^ 
正数补0负数补1
结果: 125>>3 = 0000 1111 = 15
等价与 125/2的3次方的商

左移(<<)

同样的，左移则是将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
125>>3

1
2
3
4
5
6
7
8
9
10
11
12
           125   >>    3
右移:    
      0 1 1 1 1 1 0 1
      ---------------
    0|1 1 1 1 1 0 1 0  << 1
  0 1|1 1 1 1 0 1 0 0  << 2
0 1 1|1 1 1 0 1 0 0 0  << 3
                ^ ^ ^
                 补0
结果: 125<<3 = 1110 1000 = -24(八位)       
      125<<3 = 1110 1000 = 1000(十六位)
相当:125*2的3次方(若左移时舍弃的高位不包含1)

无符号右移(>>>)

无符号右移则始终补0，不考虑正负数。

‘ >> ‘与’ >>> ‘的区别

  • >>运算符可以将int和long视为32位和64位无符号整数类型

  • >>>也是找到两个(大)整数的舍入平均值的安全有效方法：

    1 int mid = (low + high) >>> 1;

    如果整数high和low接近最大的机器整数，则以上内容是正确的，但

    1 int mid = (low + high) / 2;

    可能由于溢出而得到错误的结果。

    这是一个示例用法，它修复了天真的二进制搜索中的错误。

  • 区别：

    • >>> 负数高位补 0；
    • >> 负数高位补1；

在这里插入图片描述在这里插入图片描述

总结:

符号 描述 运算规则
~ 反 1变0，0变1
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
>> 右移 各二进位全部左移若干位，高位丢弃，低位补0
<< 左移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）