JDK源码内的位运算是真的多啊,看得头晕,今天就来整理一下java中的位运算。
位运算有以下几种:
- & 逻辑与,按位进行与运算
- | 逻辑或,按位进行或运算
- ~ 逻辑非运算,按位取反
- ^ 逻辑异或运算
- << 位左移运算
- >> 位右移运算
& 逻辑与,按位进行与运算
1&1=1
1&0=0
0&0=0
| 逻辑或,按位进行或运算
1|1=1
1|0=1
0|0=0
~ 逻辑非运算,按位取反
这里涉及到原码、反码与补码
正数的原码反码补码都一样,负数的反码为其原码符号位后按位取反,补码为其反码+1
在计算机中,使用补码表示一个负数,想要知道该负数的十进制数是多少,必须将补码转化为原码,才能直接转十进制。
例如:
11101,第一位为符号位,则该二进制数为负数,其为一个负数的补码,先由补码转反码
即反码=补码-1,反码=11100
原码=反码除符号位,其他按位取反,原码=10011,则该负数为-3
那么~3=~00011,第一位为符号位
~00011按位取反为11100,其为一个负数的补码,则反码为11011,原码为10100,即为-4
当然只要记住一个公式就好
~x=-(x+1)
则
~3=-(3+1)=-4
~(-4)=-(-4+1)=3
^ 逻辑异或运算
1^2=3
1的二进制01,2的二进制10,按位进行异或运算,相异为1
01
10
——
11
则结果为3
<< 位左移运算,箭头往左边指,即左移
1<<2=4
1的二进制为1,左移2位,则从右边开始添加2个0,变成100,即为4
左移相当于乘法,1<<2=1*2的2次方,即为4
>> 位右移运算,箭头往右边指,即右移
15>>2=3
15的二进制为1111,右移2位,变为0011,即为3
右移相当于除法,15/2的2次方,等于3.75,舍去小数点,即为3
那我们在日常的工作中,也用不到位运算啊,而且位运算不易理解,可读性又差。
不过呢,理解位运算,可以帮助我们去理解jdk中的源码。位运算只是不易被人理解,却易被机器理解,机器执行位运算的效率非常高。
下面来几道有趣的试题。
有8瓶水,其中一瓶有剧毒,其他无毒。老鼠喝下毒药一个小时后即死。现在给你3只老鼠,如何在一个小时后测试出哪瓶水中有毒药?
这道题,如果没学过二进制的人,估计很难下手。
我们将8瓶水依次编号,分别为0,1,2,3,4,5,6,7。
三只老鼠,分别作为一个bit位,一共3个bit位。
那么有:
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
左边三位数其中的1代表老鼠喝掉当前序号的水,0代表没喝。右边的数代表水的序号。
如果第一只老鼠死了,第二只老鼠没死,第三只老鼠死了。第一只老鼠死了必然说明它喝的水中有一瓶是毒药,则三位二进制第一位为1,则4,5,6,7号水其中一瓶有毒;第二只老鼠没死,说明喝的水中必然没有毒药,排除掉6,7,此时仅剩4,5;第三只老鼠死了,则直接取到5,说明序号为5的水中有毒。
当然也可以直接利用101直接得出5。
再来一道:
有一个数组,其中有一个数字不重复,其余数字全部重复一次,找出这个不重复的数字。
这道题利用异或运算,相同的数字异或为0,0再与那个单独的数字异或,就可以得到那个不重复的数字
package com.yang.testBit;
public class TestBitMain {
public static int getUniqueNum(int arr[]) {
int num = -1;
if (arr == null || arr.length == 0) {
return num;
}
num = arr[0];
int len = arr.length;
for (int i = 1; i < len; i++) {
num = num ^ arr[i];
}
return num;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 3};
System.out.println(getUniqueNum(arr));
}
}
输出:
在上面那道题改变一下条件:
如果不重复的数字有两个怎么办?
解决办法是先遍历一遍数组,异或得到一个数num,这个数就是只出现一次的那两个数异或的结果,然后找到num最低为1的位(假设是第i位),再次遍历数组,按第i位为1和为0将数组分为两个数组,此时只出现一次的两个数就被分到了不同的组,然后对每个组按照上面最初的方法找出来就可以了。
再来一道:
交换两个数?
我们利用异或运算,a^b^b=a^(b^b)=a^0=a
例如:
public static void swap() {
int a = 3;
int b = 5;
System.out.println("交换前:a=" + a + " b=" + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("交换后:a=" + a + " b=" + b);
}
输出:
位运算也是挺有趣的嘛