异或运算:
首先异或表示当两个数的二进制表示, 进行异或运算时, 当前位的两个二进制表示不同则为 1 相同则为 0. 该方法被广泛推广用来统计一个数的 1 的位数!
参与运算的两个值, 如果两个相应 bit 位相同, 则结果为 0, 否则为 1.
即:
- 0^0 = 0,
- 1^0 = 1,
- 0^1 = 1,
- 1^1 = 0
按位异或的 3 个特点:
(1) 0^0=0,0^1=1 0 异或任何数 = 任何数
(2) 1^0=1,1^1=0 1 异或任何数 - 任何数取反
(3) 任何数异或自己 = 把自己置 0
按位异或的几个常见用途:
(1) 使某些特定的位翻转
例如对数 10100001 的第 2 位和第 3 位翻转, 则可以将该数与 00000110 进行按位异或运算.
10100001^00000110 = 10100111
(2) 实现两个值的交换, 而不必使用临时变量.
例如交换两个整数 a=10100001,b=00000110 的值, 可通过下列语句实现:
- a = a^b; //a=10100111
- b = b^a; //b=10100001
- a = a^b; //a=00000110
位运算
位运算时把数字用二进制表示之后, 对每一位上 0 或者 1 的运算. 理解位运算的第一步是理解二进制. 二进制是指数字的每一位都是 0 或者 1. 比如十进制的 2 转化为二进制之后就是 10.
其实二进制的运算并不是很难掌握, 因为位运算总共只有 5 种运算: 与, 或, 异或, 左移, 右移. 如下表:
与(&) | 0 & 0 = 0 | 1 & 0 = 0 | 0 & 1 = 0 | 1 & 1 = 1 |
或(|) | 0 | 0 = 0 | 1 | 0 = 1 | 0 | 1 = 1 | 1 | 1 = 1 |
异或(^) | 0 ^ 0 = 0 | 1 ^ 0 = 1 | 0 ^ 1 = 1 | 1 ^ 1 = 0 |
左移运算:
左移运算符 m<<n 表示吧 m 左移 n 位. 左移 n 位的时候, 最左边的 n 位将被丢弃, 同时在最右边补上 n 个 0. 比如:
- 00001010 <<2 = 00101000
- 10001010 << 3 = 01010000
右移运算:
右移运算符 m>>n 表示把 m 右移 n 位. 右移 n 位的时候, 最右边的 n 位将被丢弃. 但右移时处理最左边位的情形要稍微复杂一点. 这里要特别注意, 如果数字是一个无符号数值, 则用 0 填补最左边的 n 位. 如果数字是一个有符号数值, 则用数字的符号位填补最左边的 n 位. 也就是说如果数字原先是一个正数, 则右移之后再最左边补 n 个 0; 如果数字原先是负数, 则右移之后在最左边补 n 个 1. 下面是堆两个 8 位有符号数作右移的例子:
- 00001010>> 2 = 00000010
- 10001010>> 3 = 11110001
关于移位的运算有这样的等价关系: 把整数右移一位和把整数除以 2 在数学上是等价的.
- a <<= 1 ; //a 左移一位等效于 a = a * 2;
- a << = 2 ; //a 左移 2 位等效于 a = a * 2 的 2 次方(4);
计算机内部只识别 1,0, 十进制需变成二进制才能使用移位运算符<<,>> .
- int j = 8;
- p = j <<1;
- cout<<p<<endl;
在这里, 8 左移一位就是 8*2 的结果 16 .
移位运算是最有效的计算乘 / 除乘法的运算之一.
按位与 (&) 其功能是参与运算的两数各对应的二进制位相与. 只有对应的两个二进制位均为 1 时, 结果位才为 1, 否则为 0 . 参与运算的数以补码方式出现.
先举一个例子如下:
题目: 请实现一个函数, 输入一个正数, 输出该数二进制表示中 1 的个数.
- [cpp] view plain http://blog.csdn.net/hyg0811/article/details/11516129# copy http://blog.csdn.net/hyg0811/article/details/11516129#
- int count(BYTE n)
- {
- int num = 0;
- while(n){
- n &= (n - 1);
- num++;
- }
- return num;
- }
这里用到了这样一个知识点: 把一个整数减去 1, 再和原整数做与运算, 会把该整数最右边一个 1 变成 0 . 那么一个整数的二进制表示中有多少个 1, 就可以进行多少次这样的操作.
总结: 把一个整数减去 1 之后再和原来的整数做位与运算, 得到的结果相当于是把整数的二进制表示中的最右边一个 1 变成 0 .
位运算的应用可以运用于很多场合:
清零特定位(mask 中特定位置 0, 其它位为 1 , s = s & mask).
取某数中指定位(mask 中特定位置, 其它位为 0, s = s & mask).
举例: 输入两个整数 m 和 n, 计算需要改变 m 的二进制表示中的多少位才能得到 n.
解决方法: 第一步, 求这两个数的异或; 第二步, 统计异或结果中 1 的位数.
- [cpp] view plain http://blog.csdn.net/hyg0811/article/details/11516129# copy http://blog.csdn.net/hyg0811/article/details/11516129#
- <span style="font-size:18px">#include<iostream>
- using namespace std;
- int main()
- {
- int a = 10 , b =13 , count = 0;
- int c;
- c = a ^ b;
- while(c){
- c &= (c - 1);
- count++;
- }
- cout<<count<<endl;
- return 0;
- }</span>
接下来我们再举一例, 就可以更好的说明移位运算了: 用一条语句判断一个整数是不是 2 的整数次方.
解决方法: 一个整数如果是 2 的整数次方, 那么它的二进制表示中有且只有一位是 1, 而其它所有位都是 0 . 根据前面的分析, 把这个整数减去 1 后再和它自己做与运算, 这个整数中唯一的 1 就变成 0 了.
解答:!(x & (x - 1))
来源: http://www.bubuko.com/infodetail-2631177.html