概述
Java中的位运算
(一)移位运算
左移:<<
左移1位相当于乘2,x << n等价于x * (2 ^ n)。
int i = 4; //100
i = i << 2; //10000 = 16 = 4 * (2 ^ 2)
复制代码
应用:乘法
对于h = 2 ^ n - 1来说,其中n为整数,有:
h * a =
(2 ^ n - 1) * a =
(a * 2 ^ n) - a =
(a << n) - a
有符号右移:>>
右移1位相当于除2,x >> n等价于x / 2n。
int i = 4; //100
i = i >> 2; //001 = 1 = 4 / (2 ^ 2)
复制代码
无符号右移:>>>
应用:
求某m位数c的高n位:c >>> (m - n)
如:求32位int型变量c的高16位 —— c >>> 16
(二)逻辑运算
按位与:&【有0则0】
1 & 0 = 0
1 & 1 = 1
0 & 0 = 0
1. 判断奇偶
n & 1 == 1则为奇数,n & 1 == 0则为偶数
// 1 的二进制为:000...0001
int odd = 5; //101 奇数最后一位必为1,与1按位与,一定是000...0001
int even = 6; //110 偶数最后一位必为0,与1按位与,一定是000...0000
//odd & 1 = 1,奇数
//even & 1 = 0,偶数
复制代码
2. 判断是否是2的整数次幂
n & (n-1) == 0是2 ^ n,n & (n-1) == 1不是2 ^ n
//请看:
//4:100
//3:011
//8:1000
//7:0111
//可知:
//2 ^ n的二进制码必定是1000...000的格式,除了首位为1,其他都为0
//2 ^ n - 1的二进制码必定是0111...111的格式,除了首位为0,其他都为1
int isTrue = 16; //10000
int isFalse = 15; //01111
//isFalse - 1 = 14 ,二进制01110
//isTrue & (isTrue - 1) = 0,2 ^ n
//isFale & (isFalse - 1) = 01110,非2 ^ n
复制代码
3. 对2的整数次幂取模
m & (n - 1)等价于m % n。
注意:n必须要是2 ^ n!!!并不所有数都可以。
// HashMap中获取元素下标
// 将key.hashCode()前16位与后16位异或,求出一个hash值,这一步是为了让元素分布更加均衡
int hash = (key == null) ? 0 : ((key.hashCode()) ^ (key.hashCode() >>> 16));
// 将hash值对数组长度取模,将hash值映射成数组位置
int index = hash & (len - 1);
// 这也是为什么HashMap的容量一定要2 ^ n的原因 —— 方便位运算取模
复制代码
4. 求某m位数的低n位:c & ((1 << (m - n)) - 1)
如:求32位int型变量c的低16位 —— c & ((1 << 16 )- 1)
按位或:|【有1则1】
1 | 1 = 1
1 | 0 = 1
0 | 0 = 0
1. HashMap中的应用:最小的2的幂次方
//该方法可以保证返回一个能容纳cap的2的幂次方
static final int tableSizeFor(int cap){
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码我们以cap = 65(1000001)为例,那么n = 64(1000000)
n >>> 1 = 0100000
n |= n >>> 1 = 1000000|0100000 = 1100000(96)
n |= n >>> 2 = 1100000|0011000 = 1111000(120)
n |= n >>> 4 = 1111000|0000111 = 1111111(127)
n |= n >>> 8 = 1111111|0000000 = 1111111(127)
n |= n >>> 16 = 1111111|0000000 = 1111111(127)
n + 1 = 128 = 2 ^ 7
按位非:~【取反】
按位异或:^【相同则0,相异为1】
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
特点:
任何数和自己异或都是0:a ^ a = 0
0和任何数异或都是该数本身:0 ^ a = a
1. HashMap中的应用:扰动函数
int hash = key.hashCode() ^ (key.hashCode() >>> 16);
//将高低16位进行异或,使得元素在HashMap上分布均匀
复制代码
2. 不用临时变量交换两个数
主要用到的原理就是a ^ (b ^ a) = b
//交换a和b的值
//a = a + b;
//b = a - b;
//a = a - b;
int a = -10;
int b = 11;
a = a ^ b;
b = a ^ b; //(a ^ b) ^ b = a
a = a ^ b; //(a ^ b) ^ (a ^ b) ^ b = b
//交换后a = 11, b = -10
//注意a和b不能是同一对象!!!!!!!
复制代码
警惕以下情况——a和b出于某种原因,变成了同一个对象,那么以上代码都会出错:
//a = 2
a = a + a; //4
a = a - a; //0
a = a - a; //0
//a = 0
a = a ^ a; //0
a = a ^ a; //0
a = a ^ a; //0
//a = 0
复制代码
最后
以上就是踏实白羊为你收集整理的java中位运算公式_Java中的位运算的全部内容,希望文章能够帮你解决java中位运算公式_Java中的位运算所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复