位运算

写在前面:

HAOI在位运算上吃了亏,无良老师乱定义运算符,害的我and当成xor进行运算,因此考完HAOI就来补位运算。

趋向于

首先我列出来一个“趋向于”

1
while(n-->0)

没错就是这样,我原本以为是什么位运算,结果就是自减之后判断时候是否大于某一个数。在100000000之内是略快于for的,但是超过100000000之后两者速度就相差无几了,甚至for略快于while,感觉这个东西没什么卵用(写在代码里装高端)。

位运算

其次放下来一张系统的图:

这些运算符分别叫做 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.结合律(即(ab)c == a(bc))

3.对于任何数x,都有xx=0,x0=x 4、自反性 A XOR B XOR B = A xor 0 = A

然后我就列出来一个有意思的题:

【例题】1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现 一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

这里有实现方法,都是比较好理解的。

就是利用上面的结合律和交换律来实现的,将所有的数全部异或,得到的结果与1231000的结果进行异或,得到的结果就是重复数。i<=1000;i++)

1
2
3
4
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. not运算(取反运算 ~ )

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

如果是有符号的话,就是-n-1;

5. shl运算(左移运算 << )

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

6. shr运算(右移运算 >> )

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

一道神奇的题目

下面列举出来一些有意思的东西。

高低位交换

给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示(不足32位用0补足)。我们称这个二进制数的前16位为“高位”,后16位为“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多少(用十进制表示)。

这道题其实用>>和<<运算符就好,一个左移16位,另外一个右移16位,然后进行或运算。核心代码只有一行,这比用模拟快的很多而且很好写。