当前位置:首页 > 默认分类 > 正文内容

【算法】位运算与优化

virtualman6年前 (2018-08-15)默认分类2553

刚刚学算法的时候,看到dalao处处用位运算,感觉真的太玄学了,然后直到今天才深入理解了下位运算的操作,其实并没有多么玄学,只不过是利用了计算机本身的性质罢了。

基本概念:

真值:

带符号位的机器数对应的真正数值称为机器数的真值
0000 0001的真值 = +000 0001 = +1,1000 0001的真值 = –000 0001 = –1

原码:

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值
PS:正数的原、反、补码都一样:0的原码跟反码都有两个,因为这里0被分为+0和-0。

反码:

正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变,其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反

补码:

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

PS:0的补码是唯一的,如果机器字长为8那么[0]补=00000000。

移码:

移码最简单了,不管正负数,只要将其补码的符号位取反即可。

例如:X=-101011 , [X]原= 10101011 ,[X]反=11010100,[X]补=11010101,[X]移=01010101

位运算基本运算符:

&:按位与
|:按位或
^:按位异或(相同为1,不同为0)
~:取反
<<:左移
>>:右移

常用位运算优化方法:

1.判断整数奇(1)偶(0)性:

bool IsOdd(int x)//判断是否为奇数{    return x&1;
}

 

2.乘以或除以2的幂:

 

列如:    乘以2: x<<1;
     乘以2的n次方:x<<n;
     除以2:x>>2;
     除以2的n次方:x>>n;
变式:    计算2的n次方:2<<(n-1);

 

3.比较两个数是否相等:

计算两个数的异或值,若等于0,则两数相等。

bool IsEqual(int a,int b)
{    return !(a^b);
}

 

4.不使用第三方变量交换a,b:

int a,int b;
a=a^=a^=a^b;

 

5.判断两个数是否同号:

!((a^b)>>31);

 

6.求n的绝对值:

(n^(n>>31))-(n>>31);

 

7.提取lowbit():

int lowbit(int x)
{    return x&-x;
}

 

8.计算整数x和y的平均值,可防止溢出。

int average(int x, int y) //返回X,Y 的平均值 { 
  return (x&y)+((x^y)>>1); 
}

 

9.判断一个整数n是否为2的幂 2^n:

((x&(x-1))==0)&&(x!=0);


相关文章

【已解决】ubuntu16.04和Python3.5里的大坑

因为一些历史原因,几个服务器的系统都一直是ubuntu16.04,ubuntu16.04的python3的默认版本是3.5。而我这次配置python环境需要用到Pymysql配置成功后,然后直接运行,一直报错。我还一直尝试修改pymysql的代码,一度以为镜像站里的pymysql有错误。甚至跑去Gi...

跑在内存中的数据库——H2数据库

跑在内存中的数据库——H2数据库

今天接触到了一个非常有意思的数据库,叫H2数据库。在众多数据库中,H2数据库以其独特的特性——内存数据库模式,吸引了大量开发者的关注。今天,就来深入探讨一下这个跑在内存中的数据库——H2数据库。 一、H2数据库简介 H2是一个轻量级的关系型数据库,它支持嵌入式和客户...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。