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

【算法】位运算与优化

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

刚刚学算法的时候,看到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);


相关文章

【Socket通信】关于Socket通信原理解析及python实现

【Socket通信】关于Socket通信原理解析及python实现

Socket(套接字)通信{网络通信其实就是Socket间的通信},首先了解下概念:【来源于百度百科】1"两个程序通过一个双向的通信连接实现数据的交换,这个连接的一端称为一个socket。"可以这么说,Socket就是一个网络编程的接口(API),它定义了一种标准,并对TCP/I...

【算法】机器学习算法之Kmeans算法(K均值算法)

Kmeans算法(K均值算法)KMeans算法是典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。如何定义两个样本的相似:两个样本在欧式空间中的距离引入新概念:Cluster:...

python实现对简单的运算型验证码的识别【不使用OpenCV】

python实现对简单的运算型验证码的识别【不使用OpenCV】

最近在写我们学校的教务系统的手机版,在前端用户执行绑定操作后,服务器将执行登录,但在登录过程中,教务系统中有个运算型的验证码,大致是这个样子的: 下面我们开始实现这个验证码的识别。1、图片读取从网站上下载大量同类型的验证码,人工标记上每个验证码的识别结果2、图片灰度化、二值化灰度化,在RGB模型中...

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

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

Python中的selenium库的基本用法

Selenium是一个用于测试网站的自动化测试工具,支持各种浏览器包括Chrome、Firefox、Safari等主流界面浏览器,同时也支持phantomJS无界面浏览器。通过此行代码可以快速在Python中安装selenium库pip install Selenium另外,我们仍需要安装浏览器驱动...

【JAVA】如何在宝塔面板中运行java springboot项目?手把手教程

【JAVA】如何在宝塔面板中运行java springboot项目?手把手教程

1、安装Tomcat选择网站之后,点击Tomcat管理,直接选择版本安装即可。可以选择安装7、8、9这三个版本都可以。2、将JAVA项目打包在IDEA中,右击项目,选择构建package,等待打包完成后,会在target目录下生成一个.jar的文件3、将tar文件上传到宝塔中。并点击添加JAVA项目...

发表评论

访客

看不清,换一张

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