位运算

位运算

再肝HashMap之前,还是需要了解位运算滴

接上篇,我们总结了链表乃至红黑树的概念及其理解;准备去扒源码的,发现里面一堆位运算;这写的都是啥啥啥?脑海中不自觉的浮现了这个表情包,可以说再形象不过了。


哈哈哈,想想这东西搞清楚了可以更好的阅读源码乃至装逼,心情不无激动了哈。废话不多说,咱们开干!

运算符

我们知道,所有的数字及字符在计算机中都是以二进制存储的,而位运算就是直接对二进制数据进行操作。

不同于我们普通的加减乘除操作,位运算符如下:

  • 位与运算:&
  • 位或运算:|
  • 位异或运算:^
  • 位左移运算:<<
  • 位右移运算:>>
  • 无符号右移:>>>
  • 位取反运算:~

当然,和加减乘除一样,运算时有个先后顺序(先乘除后加减),位运算也有它的先后顺序;按优先级排序如下:

1 取反2 左右位移3 位与4 位异或5 位或
~<<
>>
&^|

我们知道二进制中只有0和1的概念(1 理解为在对应的位数上有值,为真!0理解为在对应的位数上没有值,为假),我们举例说明如下:

用法栗子

位与 &(同真则真,同假则假,不同则假)

  • 1 & 1 = 1;
  • 0 & 0 = 0;
  • 1 & 0 = 0;

关于10进制转二进制这里就不在赘述了(除二取余),例如:5 & 6 = 4;我们看下怎么来的:

数字二进制(8位)
50000 0101
60000 0110
取&0000 0100 = 1* 2的平方 = 4

位或 |(同真则真,同假则假,不同则真)

  • 1 | 1 = 1;
  • 0 | 0 = 0;
  • 0 | 1 = 1;

例如:5 | 6 = 7;我们看下怎么来的:

数字二进制(8位)
50000 0101
60000 0110
取&0000 0111 = 1* 2的平方 + 1* 2+1* 2的0次方 = 7

位异或 ^(同真同假则假,不同则真)

  • 1 ^ 1 = 0;
  • 0 ^ 0 = 0;
  • 0 ^ 1 = 1;

例如: 5 ^ 6 = 3;我们看下怎么来的:

数字二进制(8位)
50000 0101
60000 0110
取^0000 0011 = 1* 2+1* 2的0次方 = 3

左移(<<)

左移就是将一个二进制的数据整体向左移动,正数后面虚位补0(负数后面虚位补1,例子略);例如:2 << 2 = 8;

数字二进制(8位)
20000 0010
<< 2(左移2位)0000 1000
1* 2的三次方 = 8

右移(>>)

右移就是将一个二进制的数据整体向右移动,前面虚位补0(负数前面虚位补1,,例子略);例如: 6 >> 2 = 1;

数字二进制(8位)
60000 0110
>> 2(右移2位)0000 0001
1* 2的0次方 = 1

无符号右移>>>

无符号右移,不论正数负数都补0;因为无符号右移只在32位或64位下才有意义,这里不再讨论;

取反~

取反就是在原有的数字上加1然后取反就是了,公式如下:~ x = - (x + 1);例如:~ 5 = - (5+1) = -6;

好,至此位运算的方法已经总结完了;我们来看下结合几个简单的算法题来看下位运算具体可以怎么用,又是如何给我们的计算带来便捷的。

算法栗子

一. 交换变量

我们还记得冒泡算法,有个交换变量的过程;

大体过程如下:

int temp = 0;// 定义的临时变量
int a = 1;
int b = 2;
temp = a; a = b; b = temp;
// temp = 1; a = 2; b = 0;

这里临时变量的做法其实是用空间换时间,这样做是需要额外的存储空间的;那么我们采用位异或^运算就可以解决这个问题:

int a = 1;
int b = 2;
a = a ^ b;
b = a ^ b;
a = a ^ b;

这样就可以了?这样就可以达到交换的目的?哈哈,是不是还有点懵;别急,读懂下面这三行代码还需要知道异或运算的一些性质:

  • 位异或满足交换定律:a ^ b = b ^ a;
  • 位异或满足结合定律:(a ^ b)^ c = a ^(b ^ c);
  • 任何数和0异或都是它自己:x ^ 0 = x;

了解了这些后,我们再看看上面三个式子:

a = a ^ b; // 第一步
b = a ^ b; // 第二步
a = a ^ b; // 第三步

将 a = a^b 代入 第二步中根据异或法则(同真同假则假,不同则真):
b = a^b^b = a^0 = a;

将 b=a^b 代入 第三步中根据异或法则(同真同假则假,不同则真):
a = a^a^b = 0^b = b;

这样就完成了数值的交换,是不是有点意思了;那咱们继续!

二. 2的幂运算

假设给定一个数,我们需要判断一个数是否是2的多少次幂,如果是则返回true,不是则返回false;

通常我们怎么做呢?写一个循环,然后一直除以2当能除净且除到最后值为1时,我们判断这个值为2的幂返回true;

通常我们怎么写呢?示例如下:

public static void main(String[] args) {
    boolean f = checkMi(8);
    System.out.println(f);
}

public static boolean checkMi(float x){
    while(x>1){
        x = x/2;
    }
    return x == 1?true:false;
}

那么这种写法算是很普通的写法了,逼格不够高哈!我们来看看位运算一般怎么解决的:

public static boolean check(int x){
    int z = x&(x-1);
    return x>1 & z == 0;
}

是不是少了很多代码,也显得逼格满满!哈哈,要读懂这行代码,我们需要明白什么样的数才是2的幂。来看下列数据找下规律:

1: 0000 0001
2: 0000 0010
3: 0000 0011
4: 0000 0100
7: 0000 0111
8: 0000 1000
15:0000 1111
16:0001 0000
...以此类推,我们知道类似于这样的的高位数都是1,低位数都是0的数才能是2的幂

对于1,3,7,15这样的数都是高位是0低位都是1的数;所以此时x&(x-1)==0

三. 找不同

假如给出一个字符串s1,然后将s1字符串中字符顺序打乱,再加入一个新的字符生成一个s2,让你比较这两个字符串找出新插入的字符;

例如:String s1 = "abca";加入一个新字符"x",String s2 = "bacxa",请你设计一个算法找出新插入的字符"x";我想我们大多数人的想法就是用获取每个字符的HashCode,并记录每个字符出现的次数;然后比较两个字符串中,每个字符的出现次数;直到在s2中找到出现一次的"x"为止;算法我就不写了,感兴趣的同学可以自己尝试写下;我们这里重点说下利用位运算怎么实现:

public static void main(String[] args) {
    String s1 = "abca";
    String s2 = "bacxa";

    System.out.println(findChar(s1,s2));
}
public static char findChar(String s1, String s2){
    String s = s1 + s2;
    int first = 0;
    for(int i =0;i<s.length();i++){
        first ^= Integer.valueOf(s.charAt(i));
    }
    return (char)first;
}

有没有被惊艳到?哈哈,我们还是来看下这个算法:我们这里用了异或这个位运算(同真同假则假,不同则真);其次Integer.valueOf(s.charAt(i))是获取每个字符的Ascii码。这里就不计算每个字符的Ascii码了,就拿的值“53135”举例:

0^5^3^1^3^5 = 0^(5^5)^(3^3)^1 = 0^0^0^1 = 1;//就酱紫找到了多出来的那个数了

四. "1"个数的奇偶

假设给定一个8位的二进制,我们要统计下这个8个数字中1的个数的奇偶;若为奇数个则返回1,若为偶数个则返回0;例如:0011 0111共有5个1,则返回1;这里我们就不讨论平常的做法了哈,我们直接来位运算的实现:

public static void main(String[] args) {
    String number = "00010110";
    System.out.println(findOddEven(number));
}
public static int findOddEven(String number){
    int count = 0;
    for(int i=0;i<8;i++){
        count += Integer.parseInt(String.valueOf(number.charAt(i))) & 1;
    }
    return count & 1;
}

我们来解释下:这段代码就是运用了位与运算,Integer.parseInt(String.valueOf(number.charAt(i))) & 1取出每一个数字和1与运算;为1则count自增1;这点和我们自己写代码完全一致哈,关键是后面这句count & 1;count 是偶数返回0,是奇数返回1;我们知道用位与运算,同真则真,同假则假,不同则假;1的8位二进制是0000 0001那么任何数和它位与运算,高位都会被抵消掉变成0,那么最关键的就是看最后一位了是不是1了;很明显,最后一位为1的就是奇数,否则为偶数;这个算法正是运用了这一点;

同理,更牛掰的写法如下(但是可读性不好):

n = n^(n>>1)
n = n^(n>>2)
n = n^(n>>4)
return n & 1
//这里的n代表循环中每一个元素 这个可以自行推导下

小结:关于位运算就先总结到这儿;算法的例子皆来源于LeetCode(还是要多去上面多摩擦摩擦智商);搞懂这些后我们再来掰扯下那些源码,相信肯定不会再那么痛苦!