2015.2.26

1.C/C++位操作初窥 六大位运算符：与，或|，异或^，非~，右移位,左移位 优先级：位运算 | ^ ~ % 1.1与运算 运算规则： 1 1 == 1 1 0 == 0 0 1 == 0 0 0 == 0 //与乘法一致 运算举例： 113 = 3 即00001011 00000011 = 00000011 = 3 运用: （1）.清零 只要找一

1.C/C++位操作初窥
六大位运算符：与&，或|，异或^，非~，右移位>>,左移位 优先级：位运算 & | > ^ ~ %
1.1&与运算
运算规则：
1 & 1 == 1
1 & 0 == 0
0 & 1 == 0
0 & 0 == 0 //与乘法一致
运算举例：
11&3 = 3
即00001011 & 00000011
= 00000011 = 3
运用:
（1）.清零
只要找一个二进制数，其中各个位符合一下条件：

原来的数中为1的位，新数中相应位为0。

然后使二者进行&运算，即可达到清零目的。
例：
5（00000101）& 250（11111010）= 0
5（00000101）& 2（00000010） = 0
均可，&运算可使指定位清零。

（2）取一个数中某些指定位
若有一个整数a(2byte)，想要取其中的低字节，只需要将a与8个1按位与即可。
a 00101100 10101100
b 00000000 11111111
c 00000000 10101100
a & b = c, 达到仅保留低位目的。
（3）保留指定位：
与一个数进行“按位与”运算，此数在该位取1.
例如：有一数84，即01010100（2），想把其中从左边算起的第3，4，5，7，8位保留下来，运算如下：
01010100(2，84)&00111011(2，59) = 00010000(2，16)
（4）判断能否被2整除：
if(a&1 == 0) 等价于 if(a%2 == 0);
同理：
if(a&2 == 0) 等价于 if(a%4 == 0);
if(a&4 == 0) 等价于 if(a%8 == 0);…

1.2|或运算
运算规则：
1 | 1 == 1
1 | 0 == 1
0 | 1 == 1
0 | 0 == 0
有1得1，无1得0
计算举例：
11 | 3 = 11
即00001011 | 00000011 = 00001011 = 11
运用：
可以用一个数字记录多个布尔值

1.3.^异或运算
运算规则：
1 ^ 1 == 0
1 ^ 0 == 1
0 ^ 1 == 1
0 ^ 0 == 0
不等得1，相等得0
运用：
（1）.找单数：
Given an array of integers, every element appears twice except for one. Find that single one.
就是一个数组中，所有数字都出现了两次，只有一个没有
比如 int t = {1,2,3,3,2,1,5} 要找到5。
用异或就完美了，所有相同的都会消失，留下来的就是5了。
异或是嫉妒成双成对的。

<code><span>for</span>( int <span>i</span> = <span>0</span> ; a<span>[i]</span> != <span>'\0'</span> ; <span>i</span>++) a<span>[<span>0</span>]</span> ^= a<span>[i]</span>;
<span>return</span> a<span>[<span>0</span>]</span>;</code>

(2).不用temp值实现交换数据

<code><span>//不用temp交换两个整数</span>
<span>void</span> swap(<span>int</span>& x , <span>int</span>& y)
{
    x ^= y;
    y ^= x;
    x ^= y;
} </code>

1.4~非运算
大概只能用于数据翻转：
~y = - y -1

1.5移位符
（1）.左移位：
推广：在空间足够下：

（2）.右移位：
int n = n / 2 等价于 int n = n >> 1 等价于 int n >>= 1
m次n /= 2 等价于 n >> m;

（3）.多余的话
100 % 8 == 100 - math.floor(100 / 8) * 8 == 100 - ((100 >> 3)