Java位运算原理及使用讲解

前言

日常开发中位运算不是很常用,但是巧妙的使用位运算可以大量减少运行开销,优化算法。举个例子,翻转操作比较常见,比如初始值为1,操作一次变为0,再操作一次变为1。可能的做法是使用三木运算符,判断原始值为1还是0,如果是1,设置为0,否则设置为0.但是使用位运算,不用判断原始值,直接改变值就可以:

1^num    // num为原始值

当然,一条语句可能对代码没什么影响,但是在高重复,大数据量的情况下将会节省很多开销。

位运算符

java支持的位运算符:

  • & :按位与。

  • | :按位或。

  • ~ :按位非。

  • ^ :按位异或。

  • << :左位移运算符。

  • >> :右位移运算符。

  • <<< :无符号右移运算符。

位运算符中,除 ~ 以外,其余均为二元运算符。操作数只能为整型和字符型数据。

Java使用补码来表示二进制数,在补码表示中,最高位为符号位,正数的符号位为0,负数为1。

补码的规定如下:

对正数来说,最高位为0,其余各位代表数值本身(以二进制表示),如+42的补码为 00101010

对负数而言,把该数绝对值的补码按位取反,然后对整个数加1,即得该数的补码。

如:-1 的补码为11111111111111111111111111111111

其实是(00000000000000000000000000000001按位取反11111111111111111111111111111110+1=11111111111111111111111111111111)

为何有那么多0、1,java中int是32位的。

按位与(&)

按位与的运算规则

操作数1

0

0

1

1

操作数2

0

1

0

1

按位与

0

0

0

1

规则总结:只有两个操作数对应位同为1时,结果为1,其余全为0. (或者是只要有一个为0,结果就为0)。

举例:

 



按位或(|)

按位或的运算规则

操作数1

0

0

1

1

操作数2

0

1

0

1

按位或

0

1

1

1

规则总结:只有两个操作数对应位同为0时,结果为0,其余全为1.(或者是只要有一个操作数为1,结果就为1)。

按位非(~)

按位非的运算规则

操作数

0

1

按位或

1

0

规则总结:取反操作,1就是0,0就是1

按位异或(^)

按位异或的运算规则

操作数1

0

0

1

1

操作数2

0

1

0

1

按位异或

0

1

1

0

规则总结:两者不同为1,相同为0

左位移(<<)

符号位不变,低位补0。如:2<<2 结果为8。

当移动的位数超过数字本身的位数时,那么不就都需要补0操作,实际上不是的,java不可能做那么浪费资源的事情。在真正执行位移前,其对要移动的位数做了一些预处理,比如32处理为0,-1处理为31.

右位移(>>)

低位溢出,符号位不变,并用符号位补溢出的高位。如:-6>>2结果为-2。

无符号右移(>>>)

低位溢出,高位补0。注意,无符号右移(>>>)中的符号位(最高位)也跟着变,无符号的意思是将符号位当作数字位看待。如:-1>>>1结果为2147483647。这个数字应该比较熟悉,看两个输出语句就知道是什么了:

System.out.println(-1>>>1);
System.out.println(Integer.MAX_VALUE);

System.out.println(Integer.toBinaryString(-1>>>1));
System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));

// 输出结果为:
2147483647
2147483647
1111111111111111111111111111111
1111111111111111111111111111111

-1>>>1 竟然得到了int所能表示的最大整数,精彩。

除了使用 -1>>>1 能得到 Integer.MAX_VALUE,以下的也能得到同样的结果:

// maxInt  2147483647
System.out.println(~(1 << 31));
System.out.println((1 << -1)-1);
System.out.println(~(1 << -1));

使用位运算往往能很巧妙的实现某些算法完成一些复杂的功能。

常见使用

m*2^n

可以使用m<<n求得结果,如:

System.out.println("2^3=" + (1<<3));//2^3=8
System.out.println("3*2^3=" + (3<<3));//3*2^3=24

计算结果是不是很正确呢?如果非要说2<<-1为什么不等于0.5,前面说过,位运算的操作数只能是整型和字符型。在求int所能表示的最小值时,可以使用

//minInt -2147483648
System.out.println(1 << 31);
System.out.println(1 << -1);

可以发现左移31位和-1位所得的结果是一样的,同理,左移30位和左移-2所得的结果也是一样的。移动一个负数位,是不是等同于右移该负数的绝对值位呢?输出一下就能发现不是的。

java中int所能表示的最大数值是31位,加上符号位共32位。在这里可以有这样的位移2个法则:

  • 任何数左移(右移)32的倍数位等于该数本身。

  • 在位移运算m<<n的计算中,若n为正数,则实际移动的位数为n%32,若n为负数,则实际移动的位数为(32+n%32),右移同理。

左移是乘以2的幂,对应着右移则是除以2的幂。

判断一个数n的奇偶性

n&1 == 1?”奇数”:”偶数”

为什么与1能判断奇偶?所谓的二进制就是满2进1,那么好了,偶数的最低位肯定是0(恰好满2,对不对?),同理,奇数的最低位肯定是1.int类型的1,前31位都是0,无论是1&0还是0&0结果都是0,那么有区别的就是1的最低位上的1了,若n的二进制最低位是1(奇数)与上1,结果为1,反则结果为0.

不用临时变量交换两个数

在 int[] 数组首尾互换中,是不看到过这样的代码:

public static int[] reverse(int[] nums){  
    int i = 0;  
    int j = nums.length-1;  
    while(j>i){  
        nums[i]= nums[i]^nums[j];  
        nums[j] = nums[j]^nums[i];  
        nums[i] = nums[i]^nums[j];  
        j--;  
        i++;  
    }  
    return nums;  
}

连续三次使用异或,并没有临时变量就完成了两个数字交换,怎么实现的呢?

int a = 3, b = 4;
a = a ^ b;   // 等同于 a = b ^ a;
b = a ^ b;
a = a ^ b;
System.out.println(a);    // 4
System.out.println(b);    // 3

上面的计算主要遵循了一个计算公式:b^(a^b) = a。

我们可以对以上公式做如下的推导:

任何数异或本身结果为0.且有定理a^b=b^a。异或是一个无顺序的运算符,则 b^a^b = b^b^a,结果为0^a。

再次列出异或的计算表:

操作数1

0

0

1

1

操作数2

0

1

0

1

按位异或

0

1

1

0

可以发现,异或0具有保持的特点,而异或1具有翻转的特点。使用这些特点可以进行取数的操作。

那么0^a,使用异或0具有保持的特点,最终结果就是a。

其实java中的异或运算法则完全遵守数学中的计算法则:

  • a ^ a = 0

  • a ^ b = b ^ a

  • a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

  • d = a ^b ^ c 可以推出 a = d ^ b ^ c

  • a ^ b ^a = b












相关文章

按位与运算符(&):http://www.ibloger.net/article/2498.html

http://blog.csdn.net/goskalrie/article/details/52796360





未经允许请勿转载:程序喵 » Java位运算原理及使用讲解

点  赞 (0) 打  赏
分享到: