目录

位运算

位运算

计算机中的数在内存中都是以二进制形式进行存储的,用位运算就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高,在程序中尽量使用位运算进行操作,这会大大提高程序的性能。

位操作符

& 与运算

& 与运算 两个位都是 1 时,结果才为 1,否则为 0,如

1
2
3
4
1 0 0 1 1
& 1 1 0 0 1
------------------------------
1 0 0 0 1

| 或运算

两个位都是 0 时,结果才为 0,否则为 1,如

1
2
3
4
1 0 0 1 1
| 1 1 0 0 1
------------------------------
1 1 0 1 1

^ 异或运算

两个位相同则为 0,不同则为 1,如

1
2
3
4
1 0 0 1 1
^ 1 1 0 0 1
-----------------------------
0 1 0 1 0

~ 取反运算

0 则变为 1,1 则变为 0,如

1
2
3
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0

« 左移运算

向左进行移位操作,高位丢弃,低位补 0,如

1
2
3
4
int a = 8;
a << 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0100 0000

左移n为的值即为当前值*2^n, 如:

1
2
3
a = 8
b = a<<3 # 64
c = a * (2 ** 3) # 64

»右移运算

向右进行移位操作,对无符号数,高位补 0,对于有符号数,高位补符号位,如

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
unsigned int a = 8;
a >> 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0000 0001
​
int a = -8;
a >> 3;
移位前:1111 1111 1111 1111 1111 1111 1111 1000
移位前:1111 1111 1111 1111 1111 1111 1111 1111

有符号数和无符号数

有符号数

有符号数的定义是:字节的最高位作为符号位,其余的是数值位。例如一个字节中存储的二进制数为1100 1000,最高位1作为符号位,其余的7为 100 1000 作为数值为。

那么,符号位占据1位,就有0和1这样的两种数值,就有:

  • 如果符号位为0,那么字节中存储的数值是正数
  • 如果符号位为1,那么字节中存储的数值是负数

对于1100 1000这样的二进制数据,符号位是1,就表示负数。

在有符号数中,表示负数的算法是:

  • 把数值位中存储的二进制数据,每个位都取反,就是原来为0的值变为1,原来为1的值变为0;
  • 给对取反后的二进制数据加1,得到的数值就得到负数值;

无符号数

无符号数的定义是:没有符号位,所有的位数都是数值位。所以表示的都是正数。

例子

例一

1100 1000这个数值,如果作为有符号数看待,那么符号位是1,数值位是100 1000。所以,符号位是1,所以,这个数据是负数。然后,表示成十进制时,对数值位的操作是:

  • 数值位取反,得到011 0111;
  • 对取反后的数值 011 0111加1得到011 1000,数值位的值为56;

那么,1100 1000这个二进制数据表示为“有符号数”时,就是-56这个数值。

如果作为无符号数看待,那么,就没有符号位,所有的位数都是数值位,所以11001000都作为数值位,表示的十进制数值是200

例二

例如,0111 0011这个数值,如果当做“有符号数”看待,那么,其符号位是0,所以,表示整数,数值位是115,所以,表示正115这个数值。如果当做无符号数看待,所有位都是数值位,计算得到115这个数值,所以,表示正115。所以我们可以总结

总结

  • 无符号数,总是表示正数。所有位数都表示数值位。
  • 有符号数,可以表示正数和负数,最高位是符号位,其余位都是数值位。如果符号位是0,则表示正数;如果符号位是1,则表示负数。对于负数的表示方法是:数值位全部取反,再加1,得到的数值就是负数值。

原码、反码、补码

原码

原码的表示范围-127~-0, +0~+127, 共256个数字

正0的原码是0000 0000, 负0的原码是1000 0000, 有正0负0之分, 不符合人的习惯, 待解决.

原码有几个缺点,零分两种 +0 和 -0 。还有,在进行不同符号的加法运算或者同符号的减法运算的时候,不能直接判断出结果的正负。你需要将两个值的绝对值进行比较,然后进行加减操作 ,最后符号位由绝对值大的决定。于是反码就产生了。

反码

除符号位, 原码其余位取反而得

+0:0000 0000,-0:1111 1111 仍然有正0负0之分。

正数的反码就是原码,负数的反码等于原码除符号位以外所有的位取反

举例说明:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int类型的 3 的反码是

00000000 00000000 00000000 00000011

和原码一样没什么可说的

int类型的 -3 的反码是

11111111 11111111 11111111 11111100

除开符号位 所有位 取反

解决了加减运算的问题,但还是有正负零之分,然后就到补码了

补码

在反码的基础上加1而得

对原码的两种0同时末位加1

+0:0000 0000,-0:0000 0000(因为溢出导致8位全0)

消除了正0负0之别, 如此一来, 便节省出一个数值表示方式1000 0000, 不能浪费, 用来表示-128, -128特殊之处在于没有相应的反码原码。也可以这样考虑:

1
2
3
4
5
6
7
-1:   1111 1111
-2:   1111 1110(在-1的基础上减1,直接将补码减1即可)
-3:   1111 1101(在-2补码基础上减1,以下类似)
-4:   1111 1100
……
-127:1000 0001
-128:1000 0000

如此以来:8位补码表示范围是-128~+127因为0只有一种形式所以,仍然是256个数

若8位代表无符号数, 则表示范围是 : 0~255, 这就是为什么高级语言讲到数据类型,

正数的补码与原码相同,负数的补码为 其原码除符号位外所有位取反(得到反码了),然后最低位加1

原码,反码,补码总结

  • 正数的反码和补码都与原码相同。
  • 负数的反码为对该数的原码除符号位外各位取反。
  • 负数的补码为对该数的原码除符号位外各位取反,然后在最后一位加1  

优缺点:

  • 原码最好理解了,但是加减法不够方便,还有两个零。。
  • 反码稍微困难一些,解决了加减法的问题,但还是有有个零
  • 补码理解困难,其他就没什么缺点了

存储

计算机中的整数是用补码存储的,最高位为符号位

  • 如果最高位为0则为正数,求值的时候,直接转为10进制即可。
  • 最高位如果为1代表为负数,求值的时候,需要先把二进制的值按位取反,然后加1得到负数绝对值(相反数)的二进制码,然后转为10进制,加上负号即可。

原码,反码,补码的应用

负数的十进制和二进制转换

十进制转二进制

方法为:

  • 先转换为二进制
  • 对二进制数求反
  • 再将该二进制数加一

总而言之: 十进制数转换为二进制数求补码即为结果

例子

-32 转换为二进制

  • 第一步:32(10)=00100000(2)
  • 第二步:求反:11011111
  • 第三步:加1:11100000

所以-32(10)=11100000(2)

二进制转十进制

方法为:

  • 数值为取反
  • 对该二进制加一
  • 转换为10进制

例子

11001000 转换为十进制

  • 第一步(数值位取反): 10110111
  • 第二步(加一):10111000
  • 第三步(十进制):-56

所以11001000(2)=-56(10)

十进制数求反的规律

下面都是以10进制表示:

负数求反

负数求反等于其绝对值 -1

如:

1
2
num = -5
num1 = ~num # 4

正数求反

正数求反等于其值 +1 的负数 如:

1
2
num = 4
num1 = ~num # -5

二进制的应用场景

位操作实现乘除法

数 a 向右移一位,相当于将 a 除以 2;数 a 向左移一位,相当于将 a 乘以 2

1
2
3
a = 2
a >> 1 # ---> 1
a << 1 # ---> 4

位操作交换两数

位操作交换两数可以不需要第三个临时变量,虽然普通操作也可以做到,但是没有其效率高

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# 普通操作
def swap(a: int, b: int) ->(int,int):
  a = a + b
  b = a - b
  a = a - b
  return a,b

# 位与操作
def swap(a: int, b: int) -> (int, int):
    """
    交换两个数
    :param a:
    :param b:
    :return:
    """
    a ^= b  # a = (a^b)
    b ^= a  # b = b ^ a = b ^ a ^ b
    a ^= b  # a = a ^ b = a ^ a ^ b
    return a, b

位操作判断奇偶数

只要根据数的最后一位是 0 还是 1 来决定即可,为 0 就是偶数,为 1 就是奇数

1
2
3
if(0 == (a & 1)) {
 //偶数
}

位操作交换符号

交换符号将正数变成负数,负数变成正数

1
2
3
func reversal(a int) int {
	return ^a + 1
}
1
2
3
4
5
6
7
def reversal(a: int) -> int:
    """
    求相反数
    :param a:
    :return:
    """
    return ~a + 1

正数取反加1,正好变成其对应的负数(补码表示);负数取反加一,则变为其原码,即正数

位操作求绝对值

正数的绝对值是其本身,负数的绝对值正好可以对其进行取反加一求得,即我们首先判断其符号位(整数右移 31 位得到 0,负数右移 31 位得到 -1,即 0xffffffff),然后根据符号进行相应的操作

1
2
3
4
def abs(a: int) -> int:
    i = a >> 31
    result = a if i == 0 else ~a + 1
    return result

上面的操作可以进行优化,可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况,即 i = 0 为正,i = -1 为负。对于任何数与 0 异或都会保持不变,与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i),即整数时 a 与 0 异或得到本身,再减去 0,负数时与 0xffffffff 异或将 a 进行取反,然后在加上 1,即减去 i(i =-1)

1
2
3
4
5
6
7
8
9
def abs(a: int) -> int:
    """
    求绝对值
    :param a:
    :return:
    """
    i = a >> 31
    result = (a ^ i) - i
    return result

or

1
2
3
4
func abs(a int) int {
	i := a >> 31
	return (a ^ i) - i
}

位操作进行高低位交换

给定一个 16 位的无符号整数,将其高 8 位与低 8 位进行交换,求出交换后的值,如

从上面移位操作我们可以知道,只要将无符号数 a»8 即可得到其高 8 位移到低 8 位,高位补 0;将 a « 8 即可将 低 8 位移到高 8 位,低 8 位补 0,然后将 a » 8 和 a«8 进行或操作既可求得交换后的结果 。

1
2
unsigned short a = 34520;
a = (a >> 8) | (a << 8);

位操作统计二进制中 1 的个数

统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。

这里介绍另外一种高效的方法,同样以 34520 为例,

我们计算其 a &= (a-1)的结果:

1
2
3
4
5
6
第一次:计算前:1000 0110 1101 1000 计算后:1000 0110 1101 0000
第二次:计算前:1000 0110 1101 0000 计算后:1000 0110 1100 0000
第三次:计算前:1000 0110 1100 0000 计算后:1000 0110 1000 0000

我们发现,每计算一次二进制中就少了一个 1,则我们可以通过下面方法去统计:count = 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def count_1(a: int) -> int:
    """
    计算数值的二进制表示的1的数量
    :param a:
    :return:
    """
    count = 0
    while (a):
        a = a & a - 1
        count += 1
    return count

求和

两数求和

1
2
3
4
5
6
7
8
9
func add(a int, b int) int {
    for b != 0 {
        sum := a ^ b
        carry := (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

1
2
输入: 2
输出: [0,1,1]

示例 2:

1
2
输入: 5
输出: [0,1,1,2,1,2]
1
2
3
4
5
def countBits(num: int) -> [int]:
    result = [0] * (num + 1)
    for i in range(1, num + 1):
        result[i] = result[i & i - 1] + 1
    return result
1
2
3
4
5
6
7
func countBits(num int) []int {
    result := make([]int, num+1)
    for i := 1; i < num+1 ; i ++ {
        result[i] = result[i & (i-1)] + 1
    }
    return result
}

常用的特殊的数

0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1,奇数位为0)

0x55555555 = 1010101010101010101010101010101 (偶数位为0,奇数位为1)

0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)

0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现)

0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)

0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)

0xffffffff = 11111111111111111111111111111111