位运算总结

2017/04/29 Algorithm

总结一下位运算的相关操作。

基础运算

符号 描述 运算规则
& 都为1,结果才为1
| 都为0,结果才为0
^ 异或 相同为0,相异为1
~ 取反 0变1,1变0
>> 右移 各位右移若干位,算术右移补符号位,逻辑右移补0
« 左移 各位左移若干位,补0
  1. 只能用于int型数据
  2. 右移一般都是补符号位(算术右移)
  3. 可以用于复合运算符,例如^=, &=……

补码

计算机用补码的形式储存整型数值。正数的补码是其本身,负数的补码是由原码先取反码再加1得到的。例如:

5的原码是 0000 0101

在这里我们只看最后8位,其实计算机一般储存的是32位的整型

反码:1111 1010

反码加一:1111 1011

则-5的补码形式为 1111 1011

我们常说最高位代表的是符号位,其实符号位就是由计算出的补码自然而然生成的。在右移的时候,若为算术右移,则新出现的高位用符号位补齐,若为逻辑右移,则用0补齐。 可以通过语法区分算术右移与逻辑右移。

简单说一下用补码来表示负数的原因。计算机的本质是加法器,所以减法需要由加法来表示。负数原本是用反码表示的,这样一来正数加其负值就可以得到0。但这里出现了一个「+0和-0的问题」,即0000和1111都表示0。为了避免这个问题发明了补码,即反码加1。这样1111就会进位为10000,舍去最高位就变成了0000,解决了「+0和-0的问题」。

Java语法

&  //and
|  //or
^  //xor
~  //not
<<  //shift left
>>  //signed shift right
>>>  //unsigned shift right

Python语法

Python中如果int型达到上限则自动变为long型,故没有无符号右移的运算符。

&  #and
|  #or
^  #xor
~  #not
<<  #left shift
>>  #right shift

奇技淫巧

用位运算交换两数,把临时变量储存在a或b中再中和掉

void swap(int a, int b){
    a = a ^ b;
    b = a ^ b; // 此时 b = (a^b)^b = a^(b^b) = a^0 = a
    a = a ^ b; // 此时 a = (a^b)^a = (a^a)^b = b
    System.out.print("a=" + a);
    System.out.print("b=" + b);
}
//同样的思想用加减法或乘除法也可以实现,但容易发生溢出
void swap2(int a, int b){
		a = a-b;
		b = a+b;
		a = b-a;
    System.out.print("a=" + a);
    System.out.print("b=" + b);
}

Search

    Table of Contents