位运算总结(Bit Operation)
位运算
数字用二进制表示后的运算
无论是有符号，无符号还是其他各种类型的数。它们之间的转换的基石就是二进制的表达式没有发生改变，变得只是转换的表达式。
1.简单的布尔运算 Boolean algebra
与&,或|,非~,异或^
| 与& | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 或 | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
| 非 ~ | |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 异或 ^ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
2.逻辑运算 logical operation
逻辑运算符 &&，||，！
记住这写运算只返回 ture or false ,也就是返回 0，1
| 例子 | 运算结果 |
|---|---|
| !0x41 | 0x00 |
| !0x00 | 0x01 |
| 0x69&&0x55 | 0x01 |
还有一个重要的性质
就是当第一个参数可以评估整个表达式的时候，这个时候结束返回，不需要再去评估第二个参数了
3.移位运算 shift operation
左移，left shift operation
右移，right shift operation :
- 逻辑右移：直接进行移动填充0
- 算术右移：填补most significant value ,也就是填充符号位
00001010>>2=00000010
10001010>>3=11110001
4.还需要注意的知识点
特别提醒：
- 无符号数和有符号数之间的转换，或者是运算。要非常小心overflow
- 可以使用移位运算来代替除法，移位运算的效率更高
- 再就是一些需要积累的小技巧，例如 n&(n-1) 进行循环可以求出 n二进制表达式中的"1"的个数。
位运算的应用
剑指offer 面试题65:不用加减乘除做加法
分析的思路(三步走):
十进制分析 7+15
- 第一步:各位进行相加(不进位) 5+7=2，0+1=1 结果为12
- 第二步:做进位，5+7的进位值10
- 第三步:累加前面的结果 12+10=22
二进制的分析 5(101)+17(10001)
- 第一步: 各位进行相加，不进位
| ^ | 异或 | |||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | ||
| 1 | 0 | 1 | 0 | 0 |
- 第二步:做进位 与运算后，继续左移一个单位 才是进位值(iteration)
| & | 与 | |||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | ||
| 0 | 0 | 0 | 0 | 1 |
- 第三步: 累加前面两步的结果 （可能需要继续进位）
10100+(00001<<1)00010=10110 在运算过程中无进位
代码实现
#include <cstdio>
int Add(int num1, int num2)
{
int sum, carry;
do {
sum = num1 ^ num2;
carry = (num1 & num2) << 1; // until carry=0 return sum(num1)
num1 = sum;
num2 = carry;
}
while(num2 != 0);
return num1;
}一些相关问题
交换两个变量的值(不使用中间变量temporary)
当然在python中可以直接进行交换，这个是语言的语法
a,b=b,a # 可以直接实现元素之间的交换基于加减法
int a,b;
a=a+b;
b=a-b; // b=((a+b)-b)=a
a=a-b; // a=((a+b)-a)=b基于异或运算
a=a^b;
b=a^b; //b= (a^b)^b=a
a=a^b; //a= (a^b)^a=b
