一文搞定位运算
目录
位运算总结:
按位与 & |
同1为1 |
按位或 | |
任1为1 |
按位异或 ^ |
同1为1 |
取反 ~ |
值取反 |
左移 >> |
废弃左侧指定位数后左移,空位补0 |
右移 << |
废弃右侧指定位数后右移,空位补0 |
无符号右移 <<< |
忽略符号位的右移 |
一、前言
在现代计算机中所有的数据都是以二进制的形式存储在设备中。即0、1两种状态,计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算,即将符号位共同参与运算的运算。
我们每一种语言最终都会通过编译器转换成机器语言来执行,所以直接使用底层的语言就不需要便编译器的转换工作从而得到更高的执行效率,当然可读性可能会降低,这也是为什么汇编在大部分情况下有更快的速度。项目中合理的运用位运算能提高我们代码的执行效率。
二、加减乘除运算原理
2.1 加法和乘法
举一个简单的例子来看下CPU是如何进行计算的,比如这行代码
int a = 35;
int b = 47;
int c = a + b;
计算两个数的和,因为在计算机中都是以二进制来进行运算,所以上面我们所给的int变量会在机器内部先转换为二进制在进行相加
35: 0 0 1 0 0 0 1 1
47: 0 0 1 0 1 1 1 1
————————————————————
82: 0 1 0 1 0 0 1 0
再来看下乘法,执行如下的代码
int a = 3; int b = 2; int c = a * b;
3: 0 0 0 0 0 0 1 1 * 2
————————————————————
6: 0 0 0 0 0 1 1 0
*********************************************
int a = 3; int b = 4; int c = a * b;
3: 0 0 0 0 0 0 1 1 * 4
————————————————————
12: 0 0 0 0 1 1 0 0
*********************************************
int a = 3; int b = 8; int c = a * b;
3: 0 0 0 0 0 0 1 1 * 8
————————————————————
24: 0 0 0 1 1 0 0 0
通过以上运算可以看出当用a乘b,且如果b满足2^N的时候 就相当于把a的二进制数据向左移动N位,放到代码中 我们可以这样来写 a << N,所以上面3 * 2、3 * 4、3 * 8其实是可以写成3<<1、3<<2、3<<3,运算结果都是一样的。
那假如相乘的两个数都不满足2N怎么办呢?其实这个时候编译器会将其中一个数拆分成多个满足2N的数相加的情况,打个比方
int a = 15; int a = 15 int b = 13; => int b = (4 + 8 + 1) int c = a * b; int c = a * b
最后其实执行相乘运算就会变成这样 15 * 4 + 15 * 8 + 15 * 1,按照上文说的移位来转换为位运算就会变成15 << 2 + 15 << 3 + 15 << 0
2.2 减法和除法
减法也是与加法同理只不过计算机内减法操作就是加上一个数的负数形式,且在操作系统中都是以补码的形式进行操作(因为正数的源码补码反码都与本身相同)。首先, 因为人脑可以知道第一位是符号位, 在计算的时候我们会根据符号位, 选择对真值区域的加减. 但是对于计算机, 加减乘数已经是最基础的运算, 要设计的尽量简单. 计算机辨别"符号位"显然会让计算机的基础电路设计变得十分复杂! 于是人们想出了将符号位也参与运算的方法. 我们知道, 根据运算法则减去一个正数等于加上一个负数, 即: 1-1 = 1 + (-1) = 0 , 所以机器可以只有加法而没有减法, 这样计算机运算的设计就更简单了.
除法的话其实和乘法原理相同,不过乘法是左移而除法是右移,但是除法的计算量要比乘法大得多,其大部分的消耗都在拆分数值,和处理小数的步骤上,所以如果我们在进行生成变量的时候如果遇到多位的小数我们尽量把他换成string的形式,这也是为什么浮点运算会消耗大量的时钟周期。
操作系统中每进行一个移位或者加法运算的过程所消耗的时间就是一个时钟周期,3.0GHz频率的CPU可以在一秒执行运算3.010241024*1024个时钟周期
三、位运算
3.1 按位与 &
针对二进制,只要有一个为0,就为0.
public static void main(String[] args) {
System.out.println("2&3运算的结果是 :"+(2&3));
//打印的结果是: 2&3运算的结果是 :2
}
3.2 按位或 |
针对二进制,只要有一个为1,就为1.
3.3 按位异或 ^
针对二进制,相同的为0,不同的为1
public static void main(String[] args) {
System.out.println("2^3运算的结果是 :"+(2^3));
//打印的结果是: 2^3运算的结果是 :1
}
2 =======>0010
3 =======>0011
2^3就为0001,结果就是1
3.4 取反 ~
针对二进制,1取0,0取1
3.5 按位左移<<
针对二进制,将操作数的所有位向左移动指定的位数。
desc:转换成二进制后向左移动3位,后面用0补齐
public static void main(String[] args) {
System.out.println("2<<3运算的结果是 :"+(2<<3));
//打印的结果是: 2<<3运算的结果是 :16
}
下图展示了11111111 << 1(11111111 左移一位)的结果。
蓝色数字表示被移动位,灰色表示被丢弃位,空位用橙色的0填充。
3.6 按位右移 >>
针对二进制,将操作数的所有位向又移动指定的位数。
desc:转换成二进制后向右移动3位
public static void main(String[] args) {
System.out.println("2>>3运算的结果是 :"+(2>>3));
//打印的结果是: 2>>3运算的结果是 :0
}
下图展示了11111111 >> 1(11111111 右移一位)的结果。
蓝色数字表示被移动位,灰色表示被丢弃位,空位用橙色的0填充。
3.7 无符号按位右移 >>>
无符号右移,忽略符号位,空位都以0补齐。
二进制的最高位是符号位,0表示正,1表示负。
>>>与>>唯一的不同是它无论原来的最左边是什么数,统统都用0填充。
十进制转二进制时,因为二进制数一般分8位、 16位、32位以及64位表示一个十进制数,所以在转换过程中,最高位会补零。在计算机中负数采用二进制的补码表示,十进制转为二进制得到的是源码,将源码按位取反得到的是反码,反码加1得到补码。
比如byte是8位的,-1表示为byte型是11111111(补码表示法),-1>>>4就是无符号右移4位,即00001111,这样结果就是15。
public static void main(String[] args) {
System.out.println("16>>2运算的结果是 :"+((16)>>2));
//打印的结果是: 16>>2运算的结果是 :4
}
public static void main(String[] args) {
System.out.println("-16>>2运算的结果是 :"+((-16)>>2));
//打印的结果是: -16>>2运算的结果是 :-4
}
public static void main(String[] args) {
System.out.println("16>>>2运算的结果是 :"+((16)>>>2));
//打印的结果是: 16>>>2运算的结果是 :4
}
public static void main(String[] args) {
System.out.println("-16>>>2运算的结果是 :"+((-16)>>>2));
//打印的结果是: -16>>>2运算的结果是 :1073741820
}
可见正数做>>>运算的时候和>>是一样的。区别在于负数运算
3.8 总结
位运算应用口诀
清零取反要用与,某位置一可用或
若要取反和交换,轻轻松松用异或
移位运算要点
1 、它们都是双目运算符,两个运算分量都是整形,结果也是整形。
2 、右移运算符>>:右边的位被挤掉,对于左边多出的空位,如果是正数则空位补0,若为负数,可能补0或补1,这取决于所用的计算机系统。
3、 左移运算符<<:左边的位被挤掉,对于右边移出的空位一概补上0。
位运算符的应用
参数:源操作数s ,掩码mask
(1) 按位与&
1 、清零特定位 (mask中特定位置0,其它位为1,s=s&mask)
2、 取某数中指定位 (mask中特定位置1,其它位为0,s=s&mask)
(2) 按位或 |
常用来将源操作数某些位置1,其它位不变。
(mask中特定位置1,其它位为0 s=s |mask)
(3) 位异或 ^
1、 使特定位的值取反 (mask中特定位置1,其它位为0 s=s^mask)
2 、不引入第三变量,交换两个变量的值
二进制补码运算公式
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较
四、位运算应用
4.1 常用位运算
(1) 判断int型变量a是奇数还是偶数
a&1 = 0 偶数
a&1 = 1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1
(3) 将int型变量a的第k位清0,即a=a&~(1<<k)
(4) 将int型变量a的第k位置1,即a=a|(1<<k)
(5) int型变量循环左移k次,即a=a<<k|a>>16-k (设sizeof(int)=16)
(6) int型变量a循环右移k次,即a=a>>k|a<<16-k (设sizeof(int)=16)
(7)整数的平均值
对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0);
}
(9)不用temp交换两个整数
三种交换算法的总结 t=a; a=b; b=t; 优点:不会溢出,可用于多种数据类型(指针,字符串等) 缺点:多用一个变量 a=a+b; b=a-b; a=a-b; 优点:不增加变量。缺点:可能数值溢出。不能用于非数值交换
a ^= b; b ^= a; a ^= b; (a^=b^=a^=b;) 优点:速度快,不会数值溢出 缺点:只能用于整型量交换
(10)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(11)取模运算转化成位运算 (在不产生溢出的情况下):a % (2^n) 等价于 a & (2^n - 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下):a * (2^n) 等价于 a<< n
(13)除法运算转化成位运算 (在不产生溢出的情况下):a / (2^n) 等价于 a>> n
例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1
(15) if (x == a) x= b; else x= a; 等价于 x= a ^ b ^ x;
(16) x 的相反数 表示为 (~x+1)
4.2 颜色转换
背景
打个比方设计师再给我们出设计稿的时候通常会在设计稿上按照16进制的样子给我们标色值。但是iOS中的UIColor并不支持使用十六进制的数据来初始化。所以我们需要将十六进制的色值转换为UIColor。
原理分析
UIColor中通常是用传入RGB的数值来初始化,而且每个颜色的取值范围是十进制下的0~255,而设计同学又给的是十六进制数据,所以在操作系统中需要把这两种进制的数据统一成二进制来进行计算,这就用到了位运算。这里用一个十六进制的色值来举例子比如0xffa131我们要转换就要先理解其组成
- 0x或者0X:十六进制的标识符,表示这个后面是个十六进制的数值,对数值本身没有任何意义
- ff 颜色中的R值,转换为二进制为 1111 1111
- a1 颜色中的G值,转换为二进制为 1010 0001
- 31 颜色中的B值,转换为二进制为 0011 0001
- 上述色彩值转换为二进制后为1111 1111 1010 0001 0011 0001(每一位十六进制的对应4位二进制,如果位数不够记得高位补零)
通常来讲十六进制的颜色是按照上面的RGB的顺序排列的,但是并不固定,有时候可能会在其中加A(Alpha)值,具体情况按照设计为准,本文以通用情况举例。
综上,我们只需把对应位的值转换为10进制然后/255.0f就可得到RGB色彩值,从而转换为UIColor。
转换代码
先列出代码,后续解析
- (UIColor *)colorWithHex:(long)hexColor alpha:(float)opacity
{
//将传入的十六进制颜色0xffa131 转换为UIColor
float red = ((hexColor & 0xFF0000) >> 16)/255.0f;
float green = ((hexColor & 0xFF00) >> 8)/255.0f;
float blue = (hexColor & 0xFF)/255.0f;
return [UIColor colorWithRed:red green:green blue:blue alpha:opacity];
}
大概原理可以看出将RGB每个值都解析出来然后变成UIColor,先拿第一步转换红色值来说,我们按照运算顺序一步步来讲(默认将参数代入,用0xffa131代替hexColor)
- 0xffa131 & 0xFF0000
我们知道红色值是前两位也就是ff,所以这一步我们既然要取出红色值就要把其他位全部置零来排除干扰,这步操作便是如此,在计算机系统内是二进制来实现的,即:
1111 1111 1010 0001 0011 0001
------------------------------------------- => & => 1111 1111 0000 0000 0000
1111 1111 0000 0000 0000 0000
这部操作做完后可以看出将除了R值之外的G值B值全部置零了,但是离最终结果还差点,因为0xFF是1111 1111,而我们的结果后面多出了16个0,所以便有了第二步操作
- >> 16
将上一步得到的结果右移16位即得到0000 0000 0000 0000 1111 1111高位的零可以忽略,这也是最终的结果
- / 255.0f
这一步应该都知道UIColor中传入的数值范围在0~1,所以我们要做下转换
- 后续的G值和B值都是一样的,只是大家注意位数就可以了,值得注意的是两个二进制数进行位运算一定保证两个数的位数相同,位数不够的那个数高位要用0补齐
4.3 枚举
关于枚举中使用位运算我们之前也讲过,下面我们自己来写一个枚举(伪代码)
typedef NS_OPTIONS(NSUInteger, TestOptions) {
TestOptionOne = 1 << 0, (000001)
TestOptionTwo = 1 << 1, (000010)
TestOptionThree = 1 << 2, (000100)
TestOptionFour = 1 << 3, (001000)
TestOptionFive = 1 << 4, (010000)
TestOptionSix = 1 << 5, (100000)
上面的枚举我后面用括号表明了位移后对应的二进制的值。这样写枚举的好处是我可以对其中选项多选比如TestOptionOne | TestOptionTwo (000001 | 000010 => 000011) 或者有其他的自定义组合。
4.4 加密
在iOS中我们可以利用异或来进行加解密,异或的特性如下
A ^ B = C => C ^ A = B => C ^ B = A
上文我们可以把A认为是需要加密的数据,B认为是** C是加密后的数据,比如:
#include <stdio.h>
main()
{
char a[]="MyPassword"; /*要加密的密码*/
char b[]="cryptographic"; /****/
int i;
/*加密代码*/
for(i=0;a[i]!='\0';i++)
a[i]=a[i]^b[i];
printf("You Password encrypted: %s\n",a);
/*解密代码*/
for(i=0;a[i]!='\0';i++)
a[i]=a[i]^b[i];
printf("You Password: %s\n",a);
}