算法题每日一练：位运算

一、前言

学习目标：

• 
  
• 掌握 原码 反码 补码 基本运算以及转换
  
• 熟练应用 与 或 非 同或 异或 应用
  
• 对于 移位运算 在题目中熟练应用，后面会出位运算的题目
  

二、概述

计算机最主要的功能是处理数值、文字、声音、图形图像等信息。

在计算机内部，各种信息都必须经过数字化编码后才能被传送、存储和处理，所有的数据以二进制的形式存储在设备中，即 0、1 这两种状态。

计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，例如下面的计算：

int a=74;

int b=58;

int c=a+b;


a  74 ：  1 0 0 1 0 1 0

b  58 :     1 1 1 0 1 0

c 132 : 1 0 0 0 0 1 0 0

十进制数字转换成底层的二进制数字之后，二进制逐位相加，满2进1。

三、原码 反码 补码

1.原码

在计算机的运算中，计算机只能做加法，减法、乘除都没法计算。原码是最简单的机器数表示法，用最高位表示符号位，其他位存放该数的二进制的绝对值。

首位的0表示正数、1表示负数。

特点：

• 
  
• 表示直观易懂，正负数区分清晰
  
• 加减法运算复杂，要先判断符号是正号还是负号、相同还是相反
  

2.反码

正数的反码还是等于原码，负数的反码就是它的原码除符号位外，按位取反。

特点：

• 
  
• 反码的表示范围与原码的表示范围相同
  
• 反码表示在计算机中往往作为数码变换的中间环节
  

3.补码

正数的补码等于它的原码，负数的补码等于反码+1。

特点：

• 
  
• 在计算机运算时，都是以补码的方式运算的，下面的位运算也是补码形式计算
  

四、基本运算

1.与

符号：&

运算规则：两个二进制位都为1时才为1，否则为0

示例：1001&1111=1001

2.或

符号：|

运算规则：两个二进制位都为0时才为0，否则为1

示例：1001&1100=1101

3.非

符号：~

运算规则：0变成1，1变成0

示例：~1001 = 0110

4.同或

符号：~

运算规则：数字相同时为1，相反为0

示例：1001~1100=1010

5.异或

符号：^

运算规则：两个二进制位相反为1，相同为0

示例：1001^0111=1110

五、移位运算

1.左移

符号：<<

运算规则：符号位不变，低位补0

示例：

a<<b 代表十进制数字a向左移动b个进位

/* 左移：

 * 左移1位，相当于原数值 * 2

 * 左移2位，相当于原数值 * 4

 * 左移n位，相当于原数值 * 2^n

 */

计算 10 << 1

10的补码：0000 1010

-----------------------

结果补码：0001 0100 ==> 正数，即 10*2=20


计算 10 << 2

10的补码：0000 1010

-----------------------

结果补码：0010 1000 ==> 正数，即 10*2^2=40


计算 10 << 3

10的补码：0000 1010

-----------------------

结果补码：0101 0000 ==> 正数，即 10*2^3=80


计算 12 << 1

12的补码：0000 1100

-----------------------

结果补码：0001 1000 ==> 正数，即 12*2=24

2.右移

符号：>>

运算规则：低位溢出，符号位不变，并用符号位补溢出的高位

示例：

a>>b 代表十进制数字a向右移动b个进位

/* 右移：

 * 右移1位，相当于原数值 / 2

 * 右移2位，相当于原数值 / 4

 * 右移3位，相当于原数值 / 2^n

 * 结果没有小数(向下取整)

 */

计算 80 >> 1

80的补码：0101 0000

-----------------------

结果补码：0010 1000 ==> 正数，即 80/2=40


计算 80 >> 2

80的补码：0101 0000

-----------------------

结果补码：0001 01000 ==> 正数，即 80/2^2=20


计算 80 >> 3

80的补码：0101 0000

-----------------------

结果补码：0000 1010 ==> 正数，即 80/2^3=10


计算 24 >> 1

12的补码：0001 1000

-----------------------

结果补码：0000 1100 ==> 正数，即 24/2=12