二进制与十进制间的转换方法

因为位运算是对二进制数进行操作，所以先来熟悉一下十进制与二进制之间的转换方法。

正整数的十进制转换二进制

要点：==除二取余，倒序排列==

解释：将一个十进制数除以二，得到的商再除以二，依此类推直到商等于一或零时为止，倒取将除得的余数，即换算为二进制数的结果

例如把52换算成二进制数，计算结果如图：

image
image

52除以2得到的余数依次为：0、0、1、0、1、1，倒序排列，所以52对应的二进制数就是110100。
由于计算机内部表示数的字节单位都是定长的，以2的幂次展开，或者8位，或者16位，或者32位….。
于是，一个二进制数用计算机表示时，位数不足2的幂次时，高位上要补足若干个0。本文都以8位为例。那么：
(52)10=(00110100)2

负整数转换为二进制

要点：==（正数除二取余，倒序排列）取反加一==

解释：将该负整数对应的正整数先转换成二进制，然后对其“取补”，再对取补后的结果加1即可

例如要把-52换算成二进制：

  1. 先取得52的二进制：00110100
  2. 对所得到的二进制数取反：11001011
  3. 将取反后的数值加一即可：11001100
    即：(-52)10=(11001100)2
image
image

小数转换为二进制

要点：==（小数）乘二取整，正序排列==

解释：对被转换的小数乘以2，取其整数部分(0或1)作为二进制小数部分，取其小数部分，再乘以2，又取其整数部分作为二进制小数部分，然后取小数部分，再乘以2，直到小数部分为0或者已经去到了足够位数。每次取的整数部分，按先后次序排列，就构成了二进制小数的序列

例如把0.2转换为二进制，转换过程如图：

image
image

0.2乘以2，取整后小数部分再乘以2，运算4次后得到的整数部分依次为0、0、1、1，结果又变成了0.2，
若果0.2再乘以2后会循环刚开始的4次运算，所以0.2转换二进制后将是0011的循环，即：
(0.2)10=(0.0011 0011 0011 …..)2
循环的书写方法为在循环序列的第一位和最后一位分别加一个点标注

二进制转换为十进制

整数二进制用数值乘以2的幂次依次相加，小数二进制用数值乘以2的负幂次然后依次相加！

比如将二进制110转换为十进制：

首先补齐位数，00000110，首位为0，则为正整数，那么将二进制中的三位数分别于下边对应的值相乘后相加得到的值为换算为十进制的结果

image
image

如果二进制数补足位数之后首位为1，那么其对应的整数为负，那么需要先取反然后再换算

比如11111001，首位为1，那么需要先对其取反，即：-00000110

00000110,对应的十进制为6，因此11111001对应的十进制即为-6

换算公式可表示为:

11111001=-00000110

               =-6

如果将二进制0.110转换为十进制：

将二进制中的三位数分别于下边对应的值相乘后相加得到的值为换算为十进制的结果

位运算

Java提供的位运算符有：左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ )，除了位非( ~ )是一元操作符外，其它的都是二元操作符。

移位运算符

移位运算符操作的对象就是二进制的位，可以单独用移位运算符来处理int型整数。

运算符 含义 例子
<< 左移运算符，将运算符左边的对象向左移动运算符右边指定的位数（在低位补0） x<<3
>> “有符号”右移运算 符，将运算符左边的对象向右移动运算符右边指定的位数。使用符号扩展机制，也就是说，如果值为正，则在高位补0，如果值为负，则在高位补1. x >>3
>>> “无符号”右移运算 符，将运算符左边的对象向右移动运算符右边指定的位数。采用0扩展机制，也就是说，无论值的正负，都在高位补0. x>>>3
image
image

以int类型的6297为例，代码如下：

1
2
3
4
5
6
7
8
System.out.println(Integer.toBinaryString(6297));   
System.out.println(Integer.toBinaryString(-6297));   
System.out.println(Integer.toBinaryString(6297>>5));   
System.out.println(Integer.toBinaryString(-6297>>5));   
System.out.println(Integer.toBinaryString(6297>>>5));   
System.out.println(Integer.toBinaryString(-6297>>>5));   
System.out.println(Integer.toBinaryString(6297<<5));   
System.out.println(Integer.toBinaryString(-6297<<5));

运行结果：

11111111111111111110011101100111
11000100
11111111111111111111111100111011
11000100
111111111111111111100111011
110001001100100000
11111111111111001110110011100000

注：x<<y 相当于 x*2y ；x>>y相当于x/2y
从计算速度上讲，移位运算要比算术运算快。
如果x是负数，那么x>>>3没有什么算术意义，只有逻辑意义。

代码演示

  1. 左移

est1、将5左移2位：

1
2
3
4
5
6
7
package com.xcy;  
  
public class Test {  
    public static void main(String[] args) {  
        System.out.println(5<<2);//运行结果是20  
    }  
}

运行结果是20，但是程序是怎样执行的呢？

首先会将5转为2进制表示形式(java中，整数默认就是int类型,也就是32位):

0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后，低位补0：

0000 0000 0000 0000 0000 0000 0001 01==00== 换算成10进制为20

  1. 右移( >> ) ，右移同理，只是方向不一样罢了(感觉和没说一样)
1
System.out.println(5>>2);//运行结果是1

还是先将5转为2进制表示形式：

0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位，高位补0：

==00==00 0000 0000 0000 0000 0000 0000 0001

  1. 无符号右移( >>> )

我们知道在Java中int类型占32位，可以表示一个正数，也可以表示一个负数。正数换算成二进制后的最高位为0，负数的二进制最高为为1

例如 -5换算成二进制后为：

1111 1111 1111 1111 1111 1111 1111 1011 (刚开始接触二进制时，不知道最高位是用来表示正负之分的，当时就总想不通。。明明算起来得到的就是一个正数-_-)

我们分别对5进行右移3位、 -5进行右移3位和无符号右移3位：

1
2
3
4
5
6
7
8
9
package com.xcy;  
  
public class Test {  
    public static void main(String[] args) {  
        System.out.println(5>>3);//结果是0  
        System.out.println(-5>>3);//结果是-1  
        System.out.println(-5>>>3);//结果是536870911  
    }  
}

我们来看看它的移位过程(可以通过其结果换算成二进制进行对比)：

5换算成二进制： 0000 0000 0000 0000 0000 0000 0000 0101

5右移3位后结果为0，0的二进制为： ==000==0 0000 0000 0000 0000 0000 0000 0000 // (==用0进行补位==)

-5换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011

-5右移3位后结果为-1，-1的二进制为：
==111==1 1111 1111 1111 1111 1111 1111 1111 // (==用1进行补位==)

-5无符号右移3位后的结果 536870911 换算成二进制：

==000==1 1111 1111 1111 1111 1111 1111 1111 // (==用0进行补位==)

通过其结果转换成二进制后，我们可以发现，==正数右移，高位用0补，负数右移，高位用1补，当负数使用无符号右移时，用0进行部位(自然而然的，就由负数变成了正数了)==

注意：笔者在这里说的是右移，高位补位的情况。正数或者负数左移，低位都是用0补。(自行测试)

小技巧：

  1. << ： 左移运算符，num << 1,相当于num乘以2
  2. >> ： 右移运算符，num >> 1,相当于num除以2
  3. >>> ： 无符号右移，忽略符号位，空位都以0补齐

与运算符

与运算符用符号“&”表示，其使用规律如下：

两个操作数中位都为1，结果才为1，否则结果为0，例如下面的程序段。

1
2
3
4
5
6
7
8
9
public class data13
{
    public static void main(String[] args)
    {
        int a=129;
        int b=128;
        System.out.println("a 和b 与的结果是："+(a&b));
    }
}

运行结果

a 和b 与的结果是：128
下面分析这个程序：
“a”的值是129，转换成二进制就是10000001，而“b”的值是128，转换成二进制就是10000000。根据与运算符的运算规律，只有两个位都是1，结果才是1，可以知道结果就是10000000，即128。

或运算符

或运算符用符号“|”表示，其运算规律如下：

两个位只要有一个为1，那么结果就是1，否则就为0，下面看一个简单的例子。

1
2
3
4
5
6
7
8
9
public class data14
{
    public static void main(String[] args)
    {
        int a=129;
        int b=128;
        System.out.println("a 和b 或的结果是："+(a|b));
    }
}

运行结果

a 和b 或的结果是：129
下面分析这个程序段：
a 的值是129，转换成二进制就是10000001，而b 的值是128，转换成二进制就是10000000，根据或运算符的运算规律，只有两个位有一个是1，结果才是1，可以知道结果就是10000001，即129。

异或运算符

异或运算符是用符号“^”表示的，其运算规律是：

两个操作数的位中，相同则结果为0，不同则结果为1。下面看一个简单的例子。

1
2
3
4
5
6
7
8
9
public class data16
{
    public static void main(String[] args)
    {
        int a=15;
        int b=2;
        System.out.println("a 与 b 异或的结果是："+(a^b));
    }
}

运行结果

a 与 b 异或的结果是：13
分析上面的程序段：a 的值是15，转换成二进制为1111，而b 的值是2，转换成二进制为0010，根据异或的运算规律，可以得出其结果为1101 即13。

非运算符

非运算符用符号“~”表示，其运算规律如下：

如果位为0，结果是1，如果位为1，结果是0，下面看一个简单例子。

1
2
3
4
5
6
7
8
public class data15
{
    public static void main(String[] args)
    {
        int a=2;
        System.out.println("a 非的结果是："+(~a));
    }
}

Java位运算相关技巧

计算机所有的运算最终都是转换为位运算和移位的操作，效率也很高，在很多场合具有很强的技巧，所以做个总结供大家学习。

交换a,b的值，不使用第三个变量？

通常使用第三个变量：

1
2
3
4
5
6
int a=3,b=4;  
int temp;  
  
temp=a；  
a=b;  
b=temp;

法一：【法一需要考虑a+b会不会超过a表达的数值范围，导致内存溢出】

1
2
3
a=a+b;  
b=a-b;         // 右边等价于a+b-b=====a  
a=a-b;           //此时b等于a,右边等价于a+b-a====b

法二：

1
2
3
a=a^b;  
b=a^b; // 右边等价于a^b^b=====a  
a=a^b; //此时b===a; 此式右边等于a^b^a=====b

实现一个函数，输入一个整数，输出为该整数的二进制表示有多少个1？

思路1：：判断该整数是否能被2整除，如果不能被2整除，则最后一位肯定为1，计数器加一，然后右移一位；

1
2
3
4
5
6
7
8
9
10
int Numberof1(int n){  
int count=0;  
while(n){  
if(n&1) // if(n%2==1)  
count++;  
  
n=n>>1;  
}  
return count；  
}

存在问题：如果把移位改为除以2，那样效率又太低，如果输入时一个负数，0x8000 0000右边移动一位，变为0xC000 0000 。而不等价于理想的右移动一位的时候相当于除以2，得0x4000 0000。这样最终就会都变为1，引起死循环；

思路2：思路1中右移n可能会导致是负数的时候造成死循环。那么我们改进，每次左移1.

1
2
3
4
5
6
7
8
9
10
11
int Numberof1(int n){  
int count=0;  
unsigned int flag=1;  
while(flag){  
if(n&flag) // 判断某位是否为1  
count++;  
  
flag=flag<<1;  
}  
return count；  
}

思路3： (n-1)&n相当于把n的最右边一个1变为0；

n-1:相当于把最右边的1变为0，左边保持不变，该1右边的0变为1；10100—减1—>10011

(n-1)&n：10100—&—10011————> 10 000

1
2
3
4
5
6
7
8
int Numberof1(int n) {  
int count=0;  
while(n){  
count++;  
n=(n-1) && n;  
}  
return count；  
}

实现一个函数不用加减乘除求两个数的和

思路：num1^num2:相当于只做加法不做进位（不同为1，相同为0，此时都为1的二进制位没有进位）；

num1&num2<<1:相当于进位（都为1，才为1.左移1位）

把上面两步相加，反复迭代即可。

1
2
3
4
5
6
7
8
9
public int add(int num1,int num2){  
int sum,carray;  
do{  
sum=num1^num2;  
carray=num1&num2<<1;  
num1=sum;  
num2=carray;  
}while(num2!=0);  
}

判断一个数是不是2的整数次方？

思路：如果一个数是2的整数次方，那么这个数的二进制表示中有且仅有一位为1. (n-1)&n那么这个数唯一的一个1就会变为0；(n-1)&n==0 就是2的整数次方。

两个整数m,n,改变多少位二进制表示才能从m变为n.

思路：求异或，然后求异或中有多少个1.

一个整形数组里面除了两个数字，其他数字都出现了两次，找出只出现了一次的两个数字。时间复杂O(n),空间O(1)

思路：如果只有一个数字是只出现了一次，其他数字都出现了两次，那么只需要异或数组中的的所有元素，最后得到的值就是那个只出现一次的数字，出现偶数次的数字都被异或得0了。a^a==0。现在是两个只出现了一次的数字，那么想办法分组，每个组里面包含一个只出现一次的数字，要保证其他一样的数字出现在同一个组里。

首先异或数组里面所有的数字得到一个结果值。由于有两个数字只出现了一次，其他数字异或抵消掉了，这两个不同的数字异或结果不等于0，结果的二进制表示中肯定至少有一位为1.我们找该结果的第一个为1的位置。这两个只出现一次的数字，肯定该对应位一个为1，一个为0.我们依据每个元素该位置是否为1分为两组，这2个不同的只出现一次的数字就被分到两个组里，数字出现两次的数字由于一样肯定会被分到同一个组里。最后，分别异或两个组，得到两个数字就是唯一出现一次的两个不同的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void findNumAppearOne(int[] a){  
if(a==null || a.length<2)  
return ;  
int sum=0;  
for(int i:a) sum^=i;  
int index=findFirstBitIs1(sum); //发现第一个为1的位置；  
  
int sum1=0;  
int sum2=0;  
for(int i:a){  
if(isBit1(i,index)) //判断i的index位置是不是1；  
sum1^=i;  
else  
sum2^=i;  
}  
System.out.println(sum1);  
System.out.println(sum2);  
}  
  
public int findFirstBitIs1(int sum){//判断从右往左的第n位置是不是1，是1返回。  
int index=0;  
while((sum&1)==0){  
sum=sum>>1;  
index++;  
}  
return index;  
}  
  
public booleam isBit1(int i,int index){  
i=i>>index;  
return (i&1)==0 ;  
}

参考来源：

  1. 二进制与十进制间的转换方法(图文教程)
  2. Java 位运算(移位、位与、或、异或、非）
  3. 与位运算相关的编程算法技巧的总结java实现