Java中的位运算

Java中的位运算

(一)移位运算

1.左移:<<

左移1位相当于乘2,x << n等价于x * (2 ^ n)

1
2
int i = 4;  //二进制100
i = i << 2; //二进制10000 = 16 = 4 * (2 ^ 2)

应用:2 ^ n - 1乘法

对于h = 2 ^ n - 1来说,其中n为整数,有:
h * a =
(2 ^ n - 1) * a =
(a * 2 ^ n) - a =
(a << n) - a


2.有符号右移:>>

右移1位相当于除2,x >> n等价于x / 2n

1
2
int i = 4; //100
i = i >> 2; //001 = 1 = 4 / (2 ^ 2)

3.无符号右移:>>>

应用:

求某m位数c的高n位:c >>> (m - n)

如:求32int型变量c的高16位 —— c >>> 16


(二)逻辑运算

1.按位与:&【有0则0】

1 & 0 = 0
1 & 1 = 1
0 & 0 = 0

(1)判断奇偶

n & 1 == 1则为奇数,n & 1 == 0则为偶数

1
2
3
4
5
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
//请看:
//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!!!并不所有数都可以。

1
2
3
4
5
6
// 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)

如:求32int型变量c的低16位 —— c & ((1 << 16 )- 1)


(5)清零最低位的1:n & (n - 1)

1
2
3
4
int i = 5;	//101
System.out.println(i & (i - 1) ); //输出:4,即100
int j = 4; //100
System.out.println(j & (j - 1) ); //输出:0,即000

(6)得到最低位的1:n & -n

1
2
3
4
int i = 5;	//101
System.out.println(i & -i); //输出:1
int j = 4; //100
System.out.println(j & -j); //输出:4

2.按位或:|【有1则1】

1 | 1 = 1
1 | 0 = 1
0 | 0 = 0

HashMap中的应用:最小的2的幂次方

1
2
3
4
5
6
7
8
9
10
//该方法可以保证返回一个能容纳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

3.按位非:~【取反】

4.按位异或:^【相同则0,相异为1】

1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1

特点:

  1. 任何数和自己异或都是0:a ^ a = 0
  2. 0和任何数异或都是该数本身:0 ^ a = a

(1)HashMap中的应用:扰动函数

1
2
int hash = key.hashCode() ^ (key.hashCode() >>> 16);
//将高低16位进行异或,使得元素在HashMap上分布均匀

(2)不用临时变量交换两个数

主要用到的原理就是a ^ (b ^ a) = b

1
2
3
4
5
6
7
8
9
10
11
12
//交换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出于某种原因,变成了同一个对象,那么以上代码都会出错:

1
2
3
4
5
6
7
8
9
10
//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中的位运算

文章作者:DragonBaby308

发布时间:2019年07月30日 - 12:44

最后更新:2020年02月01日 - 14:09

原始链接:http://www.dragonbaby308.com/bit-operation/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%