News:三分天注定,七分靠打拼,爱拼才会赢!致力打造专业IT博客。如果你对本博客有任何意见或建议请联系作者,邮箱:blog@caokuan.cn

位运算及应用

逝水无痕 276 0 条

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。Java 程序中常用的位运算包含与运算、或运算、异或运算、左移、右移、无符号右移等,每种运算都有其特殊的应用,巧妙的使用位运算不仅能解决一些特殊问题,而且在效率上也非常高。

java位运算.jpg

位运算简介

与运算(&)

参加运算的两个数据,按二进制位进行运算,负数按补码形式参加按位与运算。运算规则:

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

用途:

 1. 清零:a & 0 = 0
 2. 取数据中指定位:如果要取第 n 位的值,则找一个数将第 n 位设为1,其余位为0,将这个数与 a 相与即可找出 a 中第 n 位的值

或运算(|)

参加运算的两个数据,按二进制位进行运算,负数按补码形式参加按位或运算。运算规则:

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

用途:

对一个数据的某些位置1:数 a 如果第 n 位要置1,则找一个数的对应第 n 位为1,其余位全为零,将此数与 a 相或即可使 a 中的第 n 位置1

异或运算(^)

参加运算的两个数据,按二进制位进行异或运算。运算规则:

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

异或的几条性质:

 1. 交换律
 2. 列结合律即 (a^b)^c = a^(b^c)
 3. 对于任何数x,都有x^x = 0,x^0 = x
 4. 自反性 a^b^b = a^0 = a

用途:

 1. 使特定位翻转:数 a 如果第 n 位要翻转,则找一个数的对应第 n 位为1,其余位全为零,将此数与 a 异或即可
 2. 与0异或,保留原值:a^0 = a

左移运算(<<)

将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

右移运算(>>)

将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。操作数每右移一位,相当于该数除以2。左补 0 or 补 1 得看被移数是正还是负。

不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时,系统会将二者按右端对齐,然后进行位运算。

运算为例说明如下:我们知道在 java 语言中 long 型占4个字节,int 型占2个字节,如果一个 long 型数据与一个 int 型数据进行运算,右端对齐后,左边不足的位依下面三种情况补足:

 1. 如果整型数据为正数,左边补16个0。
 2. 如果整型数据为负数,左边补16个1。
 3. 如果整形数据为无符号数,左边也补16个0。

应用技巧

1.交换两个数字的值

不借用第三个变量实现两个数字交换数值:

int a = 10;
int b = 11;

a = a ^ b;
b = b ^ a;
a = a ^ b;

结果:a = 11;  b = 10

2.用于消除 a 的最后一位1

a = 10100
a - 1 = 10011
a & (a - 1) = 10000

用 O(1) 时间检测整数 A 是否是2的幂次

思路解析:A 如果是2的幂次,则 A 满足两个条件。

1.A > 0
2.A 的二进制表示中只有一个1

A 的二进制表示中如果只有一个1,那么使用 A&(A-1) 会将唯一的一个1消去,结果得到0,通过判断结果是否为0来得出结论即可。

计算在一个32位的整数的二进制表示中有多少个1

思路解析:由 A&(A-1) 消去 A 最后一位1知:循环使用 A&(A-1) 消去最后一位1,计算总共消去了多少次即可。

将整数 A 转换为 B,需要改变多少个 bit 位

思路解析:思考将整数 A 转换为 B,如果 A 和 B 在第 i(0<=i<32)位上相等,则不需要改变这个 bit 位,如果在第 i 位上不相等,则需要改变这个 bit 位。所以问题转化为了 A 和 B 有多少个 bit 位不相同。联想到位运算中的异或操作,相同为0,相异为1,所以问题转变成了计算 A^B 之后这个数中1的个数。而求数中1的个数,则可以使用上面例子中提到的方法解决。

3.异或应用

数组中,只有一个数出现一次,剩下的都出现两次,找出出现一次的

思路解析:利用 a^b^b=a 的特性,将所有的数求异或即可得到只出现一次的数。

数组中,只有两个数出现一次,剩下都出现两次,找出出现一次的

思路解析:有了上一题的基本的思路,我们不妨假设出现一次的两个元素是 x、y,那么最终所有的元素`异或`的结果就是 res = x^y。并且 res!=0,那么我们可以找出 res 二进制表示中的某一位是1,那么这一位1对于这两个数 x、y 只有一个数的该位置是1。对于原来的数组,我们可以根据这个位置是不是1就可以将数组分成两个部分。对分成的这两个子数组分别求异或即可得到这两个只出现一次的数。
发表我的评论
icon_mrgreen.gificon_neutral.gificon_twisted.gificon_arrow.gificon_eek.gificon_smile.gificon_confused.gificon_cool.gificon_evil.gificon_biggrin.gificon_idea.gificon_redface.gificon_razz.gificon_rolleyes.gificon_wink.gificon_cry.gificon_surprised.gificon_lol.gificon_mad.gificon_sad.gificon_exclaim.gificon_question.gif

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址