JAVA ·

JAVA程序开发按位运算的记录

忘记在哪里看到一个面试题:把int a,b的值互换,不能使用临时变量。刚开始完全懵逼,脑子里面全是浆糊,不知道如何下手。查看答案后猛地一惊,心想居然还有这种操作,真是叹为观止,真的感觉自己的基础是如此的薄弱。我们一直在追逐着各种狂拽,酷炫,吊炸天的框架,技术,以及各种库,并且乐此不疲总以为学到这些技术就有去吹牛的资本,就可以拿到高工资。其实可能,很有可能你连最基本一些编程知识都没掌握好。当然我也是其中一个,这次就系统学习下基本编程中的按位运算!下面是上面面试题的答案:

public void switchValue(int a,int b){
        a = a^b;
        b = a^b;
        a = a^b;
    }

刚开始看到这样的代码,太简单,直接,粗暴有木有!!

按位运算符

JAVA语言中有以下几种按位运算符

  • & 按位与(and)
  • | 按位或(or)
  • ^ 按位异或 (xor)
  • << 左移
  • >> 右移
  • ~ 按位取反

在上面面试题中就用的了^按位异或这个运算符。

^按位异或运算

异或运算规则:同则0,异则1。如5^8如下:

0101
1000
1101 = 13 //result

如此再看面试题的代码,假设a=5,b=8,a^8的结果是a = 13即:1101。再用a^b

1101 //a
1000 //b
0101 //b = 5 a开始的值

1101 //a
0101 //b
1011 //a = 8 b开始的值

这下就可以知道a和b的值互换了并且没有使用任何临时变量。根据以上过程对于异或就有以下几个特点:

1. A^0 = A, A^A = 0;

2. A^B^B = A;

3. A^B^C == C^A^B == B^C^A

这几条特性导致,^异或在某些方面的应用非常的适用。如题:

在一个n长度整数数组中,有一个整数出现了奇次,其他整数出现是偶次,找出这个整数?**
==在这个题目中^异或就可以更好的解决这个问题,根据以上三条特性,出现偶次的整数在^后肯定为0,奇次的整数^后肯定是本身。因此可以把数组中的整数全部^后就可以得到这个数!!==

&按位与

按位与的规则如下:同真则真,一假则假!!

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

根据以上规则如需把某个整数A的值为0,直接可以使用:A = A & 0; 其经常用来屏蔽一些二进制位。例如 n = n & 0177,0177的二进制表示为:001 111 111,上句代码就是把n中除了7个低位的二进制外,其他的全部为0。还有 n = n&0xFF就是把n中除了8个低位的二进制外,其他的全部为0。

 | 按位或

按位或的规则如下:同假则假,一真则真。

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

所以按位或常用来把某些值的某些二进制位设为1。如 A = A | 0XFF。就是把A的底八位的二进制值设置为1.

<< 左移 和 >> 右移

左移和右移是针对整数的二进制进行的。下面分别把8左移2为,把8右移2位。

0000 1000 //8的二进制表示
0010 0000 //32的二进制表示 左移2位的值
0000 0010 //2的二进制表示 右移2位的值

以上不足的位都是用0来补位。因此左移和右移可以从上看出:

A = A >> n,就是A除以2的n次方,A = A << n,就是A乘以2的n次方。

~ 取反

取反一看字义就知道取值得反值,~1 = 0,~0 = 1;

以上就是语言中的按位运算符了。或许很多代码仔都觉得这个简单,当然确实不复杂,但是在实际的代码中能否使用好,就另当别论了!给个题目:==把一个int类型的a值,转换成byte[]。(在写这篇文章前,我不知道怎么转)==

首先byte[]的长度为多少合适呢?一个int是32个bit,一个byte是8个bit。因此要用byte[]数组表示一个int的值,数组长度应该为4。


/*
// >> 24
0000 0000 0000 0000 0000 0000 1010 1010
// >> 16
0000 0000 0000 0000 1010 1010 1010 1100
// >> 8
0000 0000 1010 1010 1010 1100 0101 1011
// >> 0
1010 1010 1010 1100 0101 1011 0101 1111
&
0000 0000 0000 0000 0000 0000 1111 1111
最后结果在:
byte[0] -> 1010 1010
byte[1] -> 1010 1100
byte[2] -> 0101 1011
byte[3] -> 0101 1111
*/
public byte[] intToBytes(int n){
    byte[] bytes = new byte[4];
    bytes[0] = (byte)(n >> 24 & 0xff);
    bytes[1] = (byte)(n >> 16 & 0xff);
    bytes[2] = (byte)(n >> 8 & 0xff);
    bytes[3] = (byte)(n & 0xff);
    return bytes;
}

上面代码分析,可以看出byte数组把int值 从二进制的高位到低位每8位依次保存。因此需要注意的是当把byte数组转int值时候的高低位的问题。下面我们就看代码如何把byte数组转int值。


byte[0] -> 1010 1010 << 24 1010 1010 0000 0000 0000 0000 0000 0000
byte[1] -> 1010 1100 << 16 0000 0000 1010 1100 0000 0000 0000 0000
byte[2] -> 0101 1011 << 8 0000 0000 0000 0000 0101 1011 0000 0000
byte[3] -> 0101 1111 << 0 0000 0000 0000 0000 0000 0000 0101 1111
使用按位或 | 1010 1010 1010 1100 0101 1011 0101 1111

public int bytesToInt(byte[] bytes){
    return (bytes[0] << 24)|(bytes[1] << 16)|
         (bytes[2] << 8)|(bytes[3]);
}

上面这段代码按照逻辑分析应该是没错的。但是在运行当中却出现了问题。bytesToInt(intToBytes(200))却输出-56,但是bytesToInt(intToBytes(20))却输出20。200用二进制表示是1100 1000,负数的二进制表示:其绝对值得二进制,然后取反加1。假如a是负数其二进制表示(~|a|+1);那么-56的二进制表示如下:

0011 1000 //56 叫原码
1100 0111 //取反后 叫反码
1100 1000 //加1后 叫补码

我的个鬼这不是和200的二进制表示一样的吗?那么-56和正200的二进制是一样,计算机如何区分一个二进制数是负数和非负数?查看各种资料,浏览各种博客之后,外加上自己的验证。

得出的结论是:

==**无论是8,16,32,64位的二进制,起最高位(最左边)叫符号位,用最高位区别整数的正负:1是负数,0是正数。在一个byte是8位,其有效值是7位,最高位是符号位。这样一个byte能存储的范围:-2^7~2^7-1。这里肯定有人问为啥表示正数的时候还要-1。这是因为7位的二进制最大只能是0111 1111就是127,2^7是128,所以二进制表示正数的最大值都要-1。

证明:

bytesToInt(byte[] bytes)这个函数传入128的二进制即1000 0000。按照前面的说法这个表示的是一个负数,没错结果就是-128。传入127的二进制即0111 1111。这应该是一个正整数,结果是127,因此以上推理和说法没毛病。所以bytesToInt(byte[] bytes)这个函数中如果每个byte中存的int值超过127,其八位的二进制就是负数了。还有一点在JAVA中无论是byte,shortchar,boolean都将会在编译的时候提升到int**==。
对于这点是有点不理解:难道32位int运算比8,16这些快?还是说JVM设计之初就是这样??到底出于什么考虑呢?在stackoverflow上有这么两个关于这点的连接:参考链接一参考链接二

所以byte在进行位移运算前会提升到int,而int类型是32为的二进制。byte只有八位因此就会对byte的高位进行补码操作。根据byte的最高位进行补码。如下:

0110 1111 //byte 原码 最高是0
0000 0000 0000 0000 0000 0000 0110 1111 //根据高位补码后

1000 0101 //byte 原码 最高是1
1111 1111 1111 1111 1111 1111 1000 0101 //根据高位补码后

根据之前的分析我们在位移之前,只要最低八位,然后左移响应的位数,再依次把结果异或就可以得到正确的int值。那么怎么保持第八不变,高24位全是0呢?答案就是之前讲过的 & 0xff就可以保持低八位不变,高位全部为0。如此后:

public static int bytesToInt(byte[] bytes){
        return ((bytes[0] & 0xFF) << 24)|((bytes[1] & 0xFF) << 16)|
                ((bytes[2] & 0xFF) << 8)|(bytes[3] & 0xFF);
    }

注意加括号,左移 右移的操作优先级要高于 &。搞明白这些之后,以后有关于按位操作,就是不能脑子立刻反应也可以用笔写出来了。

一个超级牛逼的程序员。脑子里面根本没有代码,只有0和1。

秋名山上行人希,常有高手论高低,如今道路依旧在,不见当年老司机!!

参与评论