二进制的知识都在这里了
- 位操作符
- 有符号数和无符号数
- 原码、反码、补码
- 负数的十进制和二进制转换
- 十进制数求反的规律
- 二进制的应用场景
计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
一 位操作符
- & 与运算
& 与运算 两个位都是 1 时，结果才为 1，否则为 0，如
1 0 0 1 1 & 1 1 0 0 1 ------------------------------ 1 0 0 0 1
-
| 或运算
两个位都是 0 时，结果才为 0，否则为 1，如
1 0 0 1 1 | 1 1 0 0 1 ------------------------------ 1 1 0 1 1
-
^ 异或运算
两个位相同则为 0，不同则为 1，如
1 0 0 1 1 ^ 1 1 0 0 1 ----------------------------- 0 1 0 1 0
-
~ 取反运算
0 则变为 1，1 则变为 0，如
~ 1 0 0 1 1 ----------------------------- 0 1 1 0 0
-
<< 左移运算
向左进行移位操作，高位丢弃，低位补 0,如
int a = 8; a << 3; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0100 0000
-
>> 右移运算
向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如
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之分。
正数的反码就是原码，负数的反码等于原码除符号位以外所有的位取反
举例说明：
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：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
如:
num = -5 num1 = ~num # 4
-
正数求反
正数求反等于其值 +1 的负数
如:
num = 4 num1 = ~num # -5
六 二进制的应用场景
- 位操作实现乘除法
数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2
a = 2 a >> 1 # ---> 1 a << 1 # ---> 4
-
位操作 交换 两数
位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高
# 普通操作 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 就是奇数
if(0 == (a & 1)) { //偶数 }
-
位操作交换符号
交换符号将正数变成负数，负数变成正数
func reversal(a int) int { return ^a + 1 }
def reversal(a: int) -> int: """ 求相反数 :param a: :return: """ return ~a + 1
正数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数
- 位操作求绝对值
正数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作
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)
def abs(a: int) -> int: """ 求绝对值 :param a: :return: """ i = a >> 31 result = (a ^ i) - i return result
or
func abs(a int) int { i := a >> 31 return (a ^ i) - i }
-
位操作进行高低位交换
给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换，求出交换后的值，如
从上面移位操作我们可以知道，只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位，高位补 0；将 a <> 8 和 a<<8 进行或操作既可求得交换后的结果 。
unsigned short a = 34520; a = (a >> 8) | (a << 8);
-
位操作统计二进制中 1 的个数
统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。
这里介绍另外一种高效的方法，以 34520 为例，
我们计算其 a &= (a-1)的结果：
第一次：计算前：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
def count_1(a: int) -> int: """ 计算数值的二进制表示的1的数量 :param a: :return: """ count = 0 while (a): a = a & a - 1 count += 1 return count
七 附录
- 附录一：上面操作的python实现
# 位运算的常用操作
def bit_or(a: int, b: int) -> int: """ | 或 运算 :param a: :param b: :return: """ return a | b
def bit_and(a: int, b: int) -> int: """ & 与运算 :param a: :param b: :return: """ return a & b
def bit_yihuo_(a: int, b: int) -> int: """ ^ 异或运算 :param a: :param b: :return: """ return a ^ b
def bit_not(a: int) -> int: """ ~ 取反 :param a: :return: """ return ~a
def count_1(a: int) -> int: """ 计算数值的二进制表示的1的数量 :param a: :return: """ count = 0 while (a): a = a & a - 1 count += 1 return count
def abs(a: int) -> int: """ 求绝对值 :param a: :return: """ i = a >> 31 result = (a ^ i) - i return result
def reversal(a: int) -> int: """ 求相反数 :param a: :return: """ return ~a + 1
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
if __name__ == "__main__": a = 6 b = 9 c = bit_and(a, b)
-
附录二：上面操作的go实现
package main
import "fmt"
// 位运算的常用操作
//| 或运算 func bit_or(a, b int) int { return a | b }
//& 与运算 func bit_and(a, b int) int { return a & b }
//^ 异或运算 func bit_yihuo_(a, b int) int { return a ^ b }
//~ 取反 func bit_not(a int) int { return ^a }
// 求相反数 func reversal(a int) int { return ^a + 1 }
// 求绝对值 func abs(a int) int { i := a >> 31 return (a ^ i) - i }
// 求1的个数 func count_1(a int) int { count := 0 for a != 0 { a = a & (a - 1) count += 1 } return count }
// 交换两数 func swap(a, b int) (int, int) { a ^= b b ^= a a ^= b return a, b }
func main() { a := 5 b := 3 c := bit_and(a,b) fmt.Println(c) }
更多信息可以参见github:
https://github.com/russellgao/algorithm/tree/master/data_structure/bit
如果觉得有用可以分享给更多的人哦
About The Author
