位运算

[499689317]

计算机数字系统

基本概念

---

计算机常用数字系统有二进制，八进制，十进制，十六进制 计算机在处理数据时都是以二进制形式进行运算的，包括数字运算 计算机内区分有符号数字与无符号数字，比如8位bit下，有符号数字表示范围为(-2^7) - (+2^7 - 1)，无符号数字范围为0 - (2^8-1) 计算机使用补码的形式表示负数

---

进制表示

---

• 二进制表示法，由一串0,1组成数字，如：(00010110)₂，转换为十进制值为：n=1*2^4+0*2^3+1*2^2+1*2^1+0*2^0
• 八进制表示法，以0开头0-7组成数字，如：(0564301)₈，转换为十进制值为：n=5*8⁵+6*8⁴+4*8³+3*8²+0*8¹+1*8⁰
• 十进制表示法，同上
• 十六进制表示法，以0x开头0-9A-F组成数字，如：(0x230AE)₁₆，转换为十进制值为：n=2*16^4+3*16^3+0*16^2+10*16^1+14*16^0

  ---

  进制转换

  ---

  二进制转换为八进制

• (00010110)₂，从低位每隔3位取一次值得到00 010 110高位不足补0得到：(025)₈
• 八进制转二进制为上述逆过程

二进制转换为十六进制

• (00010110)₂，从低位每隔4位取一次值得到0001 0110高位不足补0得到：(15)₁₆
• 十六进制转换为二进制为上述逆过程

八进制转换为十六进制

• (025)₈，先转为二进制再转为十六进制得到：(15)₁₆
• 十六进制转八进制同理

  ---

数据表示方式

---

• 操作系统为计算机提供一个字符集，字符集为每一个字符提供相应的数字映射，如经典的ASCII码与Unicode码
• 计算机通过字符对应的数字及占用的位数来识别字符集中的每一个对应字符，与其说计算机对数据的处理本质上是对其底层二进制数字的处理
• 计算机对数字运算同样也是通过二进制位操作来完成的

  ---

常用的位运算符

//  &与运算
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
// |或运算
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
// ^异或运算
// 任何数与自身异或都为0，任何数与0异或都为本身
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
// <<左移运算，低位补0，舍弃高位(如果数字越界会丢失数据)
2 << 1 = 4
// >>右移运算，高位补0，舍弃低位(如果数字越界会丢失数据)
8 >> 2 = 2

位运算一些特性

---

• n & n - 1运算去掉二进制数n的最后一个1

  二进制数据n如果以1结尾1001则有n - 1数据1000 n & n - 1 = 1000 二进制数据n如果以0结尾1000则有n - 1数据0111 n & n - 1 = 0000

• 可以使用模板将特定二进制位进行判断

  在32位系统下，整数占用4个字节，模板1010 1010 1010 1010 1010 1010 1010 1010，表示成16进制为0xAAAAAAAA，0xAAAAAAAA & n = 0(n为2的幂)则可判断n的偶数位全为0，1在奇数位 在32位系统下，整数占用4个字节，模板0101 0101 0101 0101 0101 0101 0101 0101,表示成16进制为0x55555555，0x55555555 & n = 0(n为2的幂)则可判断n的奇数位全为0，1在偶数位

• 1 ^ n运算

  n为偶数时，结果为n+1 n为奇数时，结果为n-1

• 位运算实现整数加减

  ^运算可实现无进位加法 &运算和<<运算可实现加法中的进位

  // 无进位加法
  var a = 5 = 0101
  var b = 8 = 1000
  var n = a ^ b = 0101 ^ 1000 = 1101 = 13
  // 有进位加法
  var a = 5 = 0101
  var b = 4 = 0100
  var a1 = a ^ b = 0101 ^ 0100 = 0001
  var b1 = a & b << 1 = 0101 & 0100 << 1 = 0100 << 1 = 1000
  // 递归上述过程直到无进位结束
  var n = a1 & b1 = 0001 & 1000 = 1001 = 9

  ---