进制、位运算的介绍和应用

Posted by zhidaliao on October 23, 2016

进制介绍

概念

十六进制

由0-9,A-F组成,字母不区分大小写。与10进制的对应关系是:0-9对应0-9;A-F对应10-15

原码

一个整数,按照绝对值大小转换成的二进制数,称为原码。 比如 00000000 00000000 00000000 00000101是5的原码。

反码

将二进制数按位取反,所得的新二进制数称为原二进制数的反码。 取反操作指:原为1,得0;原为0,得1。(1变0; 0变1) 比如:将00000000 00000000 00000000 00000101每一位取反,得11111111 11111111 11111111 11111010。反码是相互的。

补码

反码加1称为补码。 也就是说,要得到一个数的补码,先得到反码,然后将反码加上1,所得数称为补码。 比如: 00000000 00000000 00000000 00000101 的反码是:11111111 11111111 11111111 11111010 那么,补码为: 11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011

负数的二进制表示

-1在计算机中如何表示:

  • 先取1的原码:00000000 00000000 00000000 00000001
  • 得反码: 11111111 11111111 11111111 11111110
  • 得补码: 11111111 11111111 11111111 11111111
  • 可见,-1在计算机里用二进制表达就是全1。16进制为:0xFFFFFFFF。

注:十六进制前缀是0x。 以0x开始的数据表示16进制,计算机中每位的权为16,即(16进制)10 = (10进制)1×16。

C,C++规定,16进制数必须以 0x开头。比如0x1表示一个16进制数。而1则表示一个十进制。另外如:0xff,0xFF,0X102A,等等。其中的x也不区分大小写。(注意:0x中的0是数字0,而不是字母O)

如何判断一个二进制数是否为负数
  • 首先看是不是无符号数,开头第一位是符号位,1表示负数,0表示正数。
  • 其次看操作系统的位数。若是8位的,1111 1111就是-1,若是16位的FFFF即是-1,若是32位的FFFF FFFF即是-1。比如10101010在8位系统下是负数,在16和32位下就不是。101在8位和8位以上的操作系统中是正数。

进制的转换

十六进制 → 十进制

方法:十六进制数从低位到高位(即从右往左)计算,第0位的权值是16的0次方,第1位的权值是16的1次方,第2位的权值是16的2次方,依次递增下去,把最后的结果相加的值就是十进制的值了。

十六进制就是逢16进1,十六进制的16个数为0123456789ABCDEF。

例:将十六进制的(2B)H转换为十进制的步骤如下:

  1. 第0位 B x 16^0 = 11;

  2. 第1位 2 x 16^1 = 32;

  3. 读数,把结果值相加,11+32=43,即(2B)H=(43)D。

二进制 → 十进制

方法:二进制数从低位到高位(即从右往左)计算,第0位的权值是2的0次方,第1位的权值是2的1次方,第2位的权值是2的2次方,依次递增下去,把最后的结果相加的值就是十进制的值了。

例:将二进制的(101011)B转换为十进制的步骤如下:

  1. 第0位 1 x 2^0 = 1;

  2. 第1位 1 x 2^1 = 2;

  3. 第2位 0 x 2^2 = 0;

  4. 第3位 1 x 2^3 = 8;

  5. 第4位 0 x 2^4 = 0;

  6. 第5位 1 x 2^5 = 32;

  7. 读数,把结果值相加,1+2+0+8+0+32=43,即(101011)B=(43)D。

十进制 → 二进制

image

位运算简介

由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。 优先级相对于 加减乘除 更低

& 两个位都为1时,结果才为1
两个位都为0时,结果才为0
^ 异或 两个位相同为0,相异为1
~ 取反 0变1,1变0
« 左移 各二进位全部左移若干位,高位丢弃,低位补0
» 右移 按二进制形式把所有的数字向右移动对应位移位数,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1。 (右移中逻辑移位的高位补0而算术移位的高位是补符号位)

Java中有三种移位运算符

<< 左移运算符,num « 1,相当于num乘以2
>> 右移运算符(算术移位),num » 1,相当于num除以2
>>> 无符号右移(逻辑移位),忽略符号位,空位都以0补齐
1073741824 |  System.out.println( 1 << 30);  // 再大就溢出了
1024	   |  System.out.println(1 << 10);
32         |  System.out.println(1 << 5);
16         |  System.out.println(1 << 4);
8          |  System.out.println(1 << 3);
4          |  System.out.println(1 << 2);
2          |  System.out.println(1 << 1);

位操作符的运算优先级比较低,因为尽量使用括号来确保运算顺序,否则很可能会得到莫明其妙的结果。比如要得到像1,3,5,9这些2^i+1的数字。写成a = 1 << i + 1是不对的,程序会先执行i + 1,再执行左移操作。应该写成a = (1 << i) + 1;

位运算

左移:

按二进制形式把所有的数字向左移动对应的位数,(最左边)高位移出(舍弃),(最右边)低位的空位补零

3 « 2,则是将数字3左移2位   

  • 首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011,
  • 然后把该数字高位(左侧)的两个零移出,其他的数字都朝左平移2位,最后在低位(右侧)的两个空位补零。
  • 得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100,转换为十进制是12。

运算规则

  • 按二进制形式把所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。
  • 当左移的运算数是int 类型时,每移动1位它的第31位就要被移出并且丢弃;
  • 当左移的运算数是long 类型时,每移动1位它的第63位就要被移出并且丢弃。
  • 当左移的运算数是byte 和short类型时,将自动把这些类型扩大为 int 型。
右移:

按二进制形式把所有的数字向右移动对应位移位数,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1。

例如11 » 2,则是将数字11右移2位

  • 11的二进制形式为:0000 0000 0000 0000 0000 0000 0000 1011
  • 把低位的最后两个数字移出,因为该数字是正数,所以在高位补零。
  • 得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是2。

常用位操作小技巧

判断奇偶

只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

交换两数
void swap(int a, int b){
	int c;
	c = a;
	a = b;
	b = c;
}
static void swap2(int a, int b){
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}
  • a = a ^ ba = (a ^ b);
  • b = a ^ bb = b ^ (a ^ b),由于一个数和自己异或的结果为0并且任何数与0异或都会不变的,所以此时b被赋上了a的值;
  • a = a ^ b 就是 a = a ^ b,等换 a = a ^ (b ^ a),所以此时a被赋上了b的值;
正数变成负数,负数变成正数
static void reverse(int a){
	a = ~a + 1;
	System.out.println(a);
}
判断正负

移位来取符号位,i = a » 31, 要注意如果a为正数,i等于0,为负数,i等于-1。

static void compare(){
		
    int a = -5;
    int b = 5;

    System.out.println( a >> 31);  // -1 
    System.out.println( b >> 31 ); // 0
}
取绝对值

位操作也可以用来求绝对值,对于负数可以通过对其取反后加1来得到正数。对-6可以这样:

1111 1010(二进制) 取反->0000 0101(二进制) 加1-> 0000 0110(二进制) 来得到6。

因此先移位来取符号位,如果i等于0,直接返回;否之,返回~a + 1。完整代码如下:

def my_abs(n)
  i = n >> 31
  return i == 0 ? n : (~n + 1)
end

现在再分析下:

  • 对于任何数,与0异或都会保持不变
  • 对于任何数, 与-1即0xFFFFFFFF异或就相当于取反。
  • 因此,n与i异或后再减i(因为i为0或-1,所以减i即是要么加0要么加1)也可以得到绝对值
def my_abs(a)
  i = a >> 31
  return ((a ^ i) - i)
end
试题:一个数组中除了一个数字出现过一次外,其余的数字都出现了两次,找出那个只出现一次的数字。
void one(){
	 int[] nums = {1, 2, 3, 4, 3, 2, 1};
	 
	 int temp = 0;
	 for (int item : nums) {
		temp = item ^ temp;
	 }
	 
	 System.out.println("temp is :"+temp);
}
试题:判断一个数是否为2的次方数,而且要求时间和空间复杂度都为常数

比较下x - 1和x的关系试试?以x=4为例。

0100 ==> 4
0011 ==> 3

两个数进行 与运算 就为0了!如果不是2的整数幂则无上述关系,反证法可证之。

void one(int n) {

	// 取绝对值
	int i = n >> 31;
	n = ((n ^ i) - i);

	// 符合返回0 ,反之不为0
	System.out.println("result is :" + (n & n - 1));
}

参考网站

二、八、十、十六进制转换(图解篇)

java移位运算符详解

负数的二进制

位运算简介及基本技巧