登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Xorex's blog

纵然希望渺茫,也要做一条有梦想的咸鱼!

 
 
 
 
 

日志

 
 
关于我

本人倒是一直被吊着打啊……

文章分类

位运算  

2017-04-24 19:34:35|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
HAOI在位运算上吃了亏,无良老师乱定义运算符,害的我and当成xor进行运算,因此考完HAOI就来补位运算。
首先我列出来一个“趋向于”  

while(n-->0)

没错就是这样,我原本以为是什么位运算,结果就是自减之后判断时候是否大于某一个数。在100000000之内是略快于for的,但是超过100000000之后两者速度就相差无几了,甚至for略快于while,感觉这个东西没什么卵用(写在代码里装高端)。
其次放下来一张系统的图:
  位运算 - Xorex - Xorexs blog
这些运算符分别叫做 and or xor not shl shr
但是C++里面只能使用and or xor 三种进行计算,其他的必须输入符号,所以以后就一直用符号计算吧,本来想的是用单词进行计算的。但是一直试到了not之后进行运算,发现not竟然是“!”。看来是没有办法全部使用单词计算了。

=== 1. and运算 & ===
and运算通常用于二进制的取位操作,例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数为偶数,最末位为1表示该数为奇数。
00101
11100
———
00100
大概就是这样相同位的两个数字都为1,则为1;若有一个不为1,则为0。

=== 2. or运算 | === 
or运算通常用于二进制特定位上的无条件赋值,例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0,对这个数or 1之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。
00101
11100
--------
11101
相同位只要一个为1即为1。 
=== 3. ^ 运算 (异或运算 xor)===
异或的符号是^。按位异或运算, 对等长二进制模式按位或二进制数的每一位执行逻辑按位异或操作. 操作的结果是如果某位不同则该位为1, 否则该位为0.
(a xor b) xor b = a
xor运算的性质 
1、交换律 
2、结合律(即(a^b)^c == a^(b^c))
3、对于任何数x,都有x^x=0,x^0=x 4、自反性 A XOR B XOR B = A xor 0 = A
然后我就列出来一个有意思的题:
【例题】1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现 一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?
这里有实现方法,都是比较好理解的。
就是利用上面的结合律和交换律来实现的,将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。i<=1000;i++)

int n,a=1,b=a[1];
cin>>n;
for(int i=2;i<=1001;i++)
b=b xor a[i];
for(int i=2;i<=1000;i++)
a=a xor i;
cout<<(b xor a)<<endl;

这种方法非常快的(其实可以用高斯定理来解决,但是这也是一种高逼格的写法)

=== 4. ~运算 ===
~运算的定义是把内存中的0和1全部取反。使用~运算时要格外小心,你需要注意整数类型有没有符号。如果~的对象是无符号整数(不能表示负数),那么得到的值就是它与该类型上界的差。
如果是有符号的话,就是-n-1;

=== 5. <<运算 ===
右移运算符,这个其实就是将二进制下的数,所以位数右移n位,然后得到一个比原来的数大n*2倍的数,可以用来*2运算。

  === 6. >>运算 ===
左移运算符,和右移是一样的,不过是除以n*2(这里二分用着应该很棒)。

下面列举出来一些有意思的东西。
高低位交换
    给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示(不足32位用0补足)。我们称这个二进制数的前16位为“高位”,后16位为“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多少(用十进制表示)。
这道题其实用>>和<<运算符就好,一个左移16位,另外一个右移16位,然后进行或运算。核心代码只有一行,这比用模拟快的很多而且很好写。



  评论这张
 
阅读(67)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018