之前刷leetcode的时候发现，有些题目用位运算实施起来非常高效，而且位运算也是面试中经常会问到的知识点，这里做一个总结。

实际上各种编程语言都提供了位运算，原理和使用基本一致，这里不做区分。

原码、反码、补码

计算机中对数字的表示有三种方式：原码，反码，补码：

原码

原码表示法在数值前面增加了一位符号位（即最高位为符号位）：正数该位为0，负数该位为1。

反码

反码表示法，正数的反码是其本身；负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

补码

补码表示法，正数的补码是其本身；负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。 (即在反码的基础上+1)

转换

1.正数，原码=反码=补码
2.负数，原码=补码符号位不变，数据位取反，尾+1

备注：原码容易被人脑直接识别并用于计算，但是对于计算机来说并不友好。所以在计算机系统中，数值一律用补码来表示、运算和存储。同时，还有一个重要原因，使用补码可以将符号位和数值域统一处理，将加法和减法统一处理。

进制转换

1.十进制到二进制：bin()
2.十进制到八进制：oct()
3.十进制到十六进制：hex()
4.转成十进制直接使用int(),float()等即可。

位运算

位与运算（&）

两数各对应的二进位相与,全1为1，否则为0。参与运算的数以补码方式出现。

应用

1.按位与运算通常用来对某些位清0或保留某些位。
例如，把a的高八位清0,保留低八位。

1
a = a&255 # 255的二进制数为0000000011111111

2.之前提到过，判断power of 2。

1
2
def isPowerOfTwo(n):  
        return (n > 0 and not(n & n-1))

3.求一个整数有多少位是0(原理同上):

1
2
3
4
count=0
while x:
    count += 1
    x &= (x-1)

4.判断奇偶数(原理:奇数最后一位为1,偶数为0)

1
2
3
4
def odd(x):
    return x&1
def even(x):
    return !(x&1)

位或运算（|）

位或运算,两数各对应的二进位相或,有1就1，全0才0。,参与运算的两个数均以补码出现。

位异或运算（^）

位异或运算,两数各对应的二进位相异或,不相同为1,否则为0。参与运算数仍以补码出现。

应用

1.数值交换无须引入第三个变量。

1
2
3
a=a^b
b=b^a
a=a^b # 原理:两次异或能还原,即a=(a^b)^b

2.求x绝对值(原理:x为正数时不做改变,为负数时取反加1)

1
2
3
4
5
6
# x为正数时y=0=0000 0000 0000 0000
# x为负数时y=-1=1111 1111 1111 1111
# 跟0异或是本身,跟1异或是取反:
def abs(x):
    y = x>>31
    return (x^y-y)

求反运算(~)

具有右结合性,其功能是对参与运算的数的各二进位按位求反。

应用

求x的相反数

1
x = ~x+1

左移(<<)

全部向左移（左移n位就是乘以2的n次方）

应用

乘法运算（若为奇数可以配合加减运算实现）

1
16<<2 # 64

右移(>>)

全部向右移（左移n位就是除以2的n次方）

应用

除法运算（若为奇数可以配合加减运算实现）

1
16>>2 # 4

备注：在左移，右移注意int的范围，超出范围会产生溢出，这里不做讨论。