[C++知识库]C语言的位运算（个人笔记）——第一篇位运算总结

? ?此为本人第一次写笔记传于网上，此时本人大二小白（欲想转码），若有错误望各位大神多加指点迷津........

? 位运算，在C/C++中有着举重若轻的地位，几乎每一个学C/C++的都要学到这个知识点。它的一些骚操作也确实很考验搬砖人的搬砖功底.........

? 异或? ^

n^n=0

n^0=n

以上是异或的基本性质，但实际操作中，异或能干什么呢？

1.找出奇数

我打个比方：已知一个数组：a[7]={1,2,2,3,4,4,3}

现在我要找出那个只出现奇数次的那个数字，那么我就要利用异或的神奇性质了：n^n=0，n^0=n

1^2^2，由于异或支持结合律和交换律，我们不妨可以这么看：1^（2^2）——那么,2^2不就等于0吗？那样子就可以：1^2^2=1^0=1了

那我们回到整个题目中：

for(i=0,temp=0;i<=6;i++)
{
  temp^=a[i];
}

内部运行：1^2^2^3^4^4^3。即是：1^(2^2)^(3^3)^(4^4)=1^0^0^0。(满足结合律和交换律嘛)

然后就找出来：1咯。

异或运算，可以非常快速地把数组中的出现次数是奇数的数字快速找出来。（这不比暴力操作轻松？）

2.异或，可用于整数类型的交换！（注意类型！）

昨天晚上，在某个C++群里有个老兄兴致勃勃地大喊了一声：xdm！我发现一个秀操作！:

arr[i]=arr[i]^arr[j]  //(1)
arr[j]=arr[i]^arr[j]  //(2)
arr[i]=arr[i]^arr[j]  //(3)

这不比传统的：

t=a;
a=b;
b=t;

好吗！（以后就换了，全改成这种）

但是

真的如此吗？

且不说这代码有秀技术的嫌疑，容易被骂......

我们从异或原理分析一下这个交换的操作：

把（1）式带入二式：arr[j]=arr[i]^arr[j]??^arr[j]?

arr[j] =arr[i]^（0）=arr[i]? ? ? ?arr[i]成功赋值给了arr[j]

对于（3）：arr[i]=arr[i]^arr[j]=arr[i]^arr[i]^arr[j]? =（0）^arr[j]=arr[j]??arr[j]成功赋值给了arr[i]

这个秀啊！

别高兴太早了：位运算只能支持整数运算！！！（也就是说——这个数组得是?int?类型的）

至于为什么......我没学汇编，c也不是很熟...不知道......反正float类型的是不行的....

所以关键还得来传统法.....秀操作容易被打....

不过，说到整数运算，位运算能实现一波不用加减乘除符号的神奇操作，待我慢慢道来.....

但在此之前，允许我把位运算符的性质先介绍一遍，因为待会的操作就是依靠这些基本性质完成的。

&? 按位与

0&0=0? ?0&1=0 1&1=1? ?1&0=0? （参与运算的两个数据按二进制进行“与”运算）

套路（两个同时为1才是1，否则都是零）? （负数按补码形式参与位运算）

在此再说说：负数、补码、原码的问题（这样下去我怎么感觉我写不完了...现在是10月二号“管他读者爱看不看->_->”....）

负数：将其相反数（说白了就是正数）的原码最高位变为1，如1的

原码为0000 0001，那么-1的原码为1000 0001；

反码是将原码的符号位（最高位）外的每一位取反，如-1反码为：1111 1110（记住从左到右第一个数1是最高位）

补码是将其反码加一：-1的补码：1111 1111

（至于为什么可以诞生二进制的操作....我怎么感觉我也可以再写一点....“万恶的思维发散”）

所以，当我们讨论——参与运算的两个数据按二进制进行“与”运算时：

（举例说明）? ? ??3? ? ? ? ? ? ? ? &? ? ? ? ? ? ? 5? ? =? ? ? ? ? ? ? 1

（实际的运算） 0000 0011? &? 0000 0101 = 0000 0001 （结果为1）

这里提一下：“与”运算有个操作是和 %?判断奇偶一样：

a & 1?== 0? ? ? ? ? ? ?这两个式子功能上是一样的 ? ? ? ? ? ? ? ? ?a % 2 == 0

因为由二进制的性质我们会发现二进制数的末尾0?是偶数， 1?是奇数。（在有人问你要代码魔改的时候你就可以用这种边缘技巧去恶心他们哈哈哈“来自某乎每日zis技巧”，但是这种东西还是别乱用好容易被打....）

接下来我们再介绍一下：

|? 或运算：

（性质）：? ?0|0=0? ?，? 0|1=1? ?， 1|0=1? ? ，? ? 1|1=1

即参与运算的两个数据有1，其结果为1（有一为一，无一为零）

? ?与? “与”运算相似：（或运算，参与运算的两个数据按二进制进行“或”运算）

（举例说明）? ? ??3? ? ? ? ? ? ? ? |? ? ? ? ? ? ? 5? ? ? =? ? ? ? ? ? ? 7

（实际运算）? ? ?0000 0011? |? ? 0000 0101? =? ?0000 0111 ??

左移运算符? ? ?<<

具体操作：右边空出的位用0填补 ， 高位左移溢出则舍弃该高位
表达式:? 14 << 2? 的?结果： 56? ?因为：

0000? 1110? ?左移两位? ?0011 1000? （化为十进制）：? 56

（嘿嘿，在此又得扩展知识点了——二进制转化为十进制....）

从最低位（最右）算起，位上的数字乘以本位的权重，权重就是2的第几位的位数减一次方。

打比方：

0011 1000? 为：? 1*2^(6-1)+1*2^(5-1)+1*2^(4-1)+0*2^(3-1)+0*2^(2-1)+0*2^(1-1)=56

然后嘛，右移运算符：? >>?就是反方向操作左移运算符而已.....在此就不讨论了......

好了，我们以上讨论完位运算符的基本性质了

开始正题——位移运算符的骚操作！

由于 ：<<?和 >>? 这两个运算符的基本性质（基于二进制）

所以：

int Mul_two(int x)
  {
     return x<<1;        //x 乘以2
    }

int  Divi_TWO(int x)
{
     return  x>>1;    //除以二
}

可以用他们的性质来完成除以二，乘以二的操作啊。

还可以这样：（在不考虑数值溢出的情况下......）

int Muti_Power(int x,int n)
{
    return  x<<n;  //乘以2的n次方
}

（本来我还想再写下去的.......但是九月二十八号开始的.......到现在10/23了......算了寒假再搞吧....功课多..........）