文章目录
位操作符
分为：
按位与：&，按二进制位与
按位或：|，按二进制位或
按位异或：^，按二进制位异或
注：他们的操作数必须是整数
按位与
代码示例：
int main() { int a = 3; int b = -5; int c = a & b; printf("%d\n", v); return 0; }
运行结果：
为什么会得到这个结果呢？
按位与的规则： 两个都是1才是1，否则0
1、首先求出3和-5的补码
3的补码：0000 0011
-5的补码：1111 1011
a & b的计算方式是：a和b存在内存中的二进制的补码进行计算的
所以相与的结果为：
3的补码：00000011
-5的补码：11111011
相与结果：00000011
但是记住：计算中存储的是补码
所以我们得到的是相与过后的补码：00000011
再转换成原码：
补码：00000011
反码：00000011
原码：00000011
再把原码换算成十进制：00000011=3
这就是按位与的规则
按位或
代码示例：
int main() { int a = 3; int b = -5; int c = a | b; printf("%d\n", c); return 0; }
运行结果：
为什么会得到这个结果呢？
按位与的规则： 只要有1就是1，两个同时为0才为0
同样还是先拿出3和-5的补码
3的补码：00000011
-5的补码：11111011
相或结果：11111011
所以我们得到的是相或过后的补码：11111011
再转换成原码：
补码：11111011
反码：11111010
原码：10000101
再把原码换算成十进制：10000101=-5（符号位=1，所以要加负号）
按位异或
代码示例：
int main() { int a = 3; int b = -5; int c = a ^ b; printf("%d\n", c); return 0; }
运行结果：
为什么会得到这个结果呢？
按位异或的规则： 相同为0，相异为1
同样还是先拿出3和-5的补码
3的补码：00000011
-5的补码：11111011
相或结果：11111000
所以我们得到的是异或过后的补码：11111000
再转换成原码：
补码：11111000
反码：11110111
原码：10001000
再把原码换算成十进制：10001000=-8（符号位=1，所以要加负号）
综合练习
练习题一
1、写代码实现：交换两个变量(不能创建临时变量)
方法一：
int main() { int a = 3; int b = 5; int c = 0;//临时变量 printf("交换前: a=%d b=%d\n", a, b); c = a; a = b; b = c; printf("交换后: a=%d b=%d\n", a, b); return 0; }
运行结果：
方法二：
int main() { int a = 3; int b = 5; int c = 0;//临时变量 printf("交换前: a=%d b=%d\n", a, b); a = a + b; b = a - b; a = a - b; printf("交换后: a=%d b=%d\n", a, b); return 0; }
运行结果：
既然不让我们创建临时变量，那么用这样的方法不是也可以实现了吗？
但是这种方法有个弊端：
如果a和b存储的数字都很大，如果相加超出了**int(整型)**的范围呢？
方法三：异或
先来看个规律：
3 ^ 3 = 0
0 ^ 5 = 5
代码示例：
int main() { int a = 3; int b = 5; int c = 0;//临时变量 printf("交换前: a=%d b=%d\n", a, b); a = a ^ b; b = a ^ b;// a ^ b ^ b：b和b相异或结果为0；a和0相异或还是为a a = a ^ b;// a ^ b ^ a printf("交换后: a=%d b=%d\n", a, b); return 0; }
运行结果：
代码剖析：
①：a = a ^ b;
②：b = a ^ b;
③：a = a ^ b;
在①中：把a异或b的值赋给a；
在②中：此时a是①中: a ^ b的结果；
所以②可以看成：b = a ^ b ^ b，b ^ b = 0，a ^ 0 = a
注意：a ^ 0中的a是原来的a = 3的值，所以把3赋值给等号左边的b
在③中： 此时a还是①中: a ^ b的结果；b相当于②的结果：a=3
所以③可以看成：a = a ^ b ^ a，a ^ a = 0, b ^ 0 = b
注意：b ^ 0中的b是原来的b = 5的值；所以把5赋值给等号左边的a
练习题二
数组
nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1] 输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
题解:
我们先不看这个顺序乱的数组,而是假设有一个顺序完整的数组
然后还需要知道^的一个特性:
a ^ a = 0
a ^ 0 = 0
异或具有交换律：a ^ b ^ c = c ^ a ^ b
图示：
那么我们把每个下标以及该下标对应的数字进行连续异或；
异或过程就是：0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 5 ^ 5 ^ 6 ^ 6 ^ 7；
我们上面已经说了相同的数字进行异或，结果是0,所以最后就是0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 0 ^ 0 ^ 7；
发现还是有相同的，继续上面步骤，结果就等于：4 ^ 7
运用上面的特性 相同异或为0，我们发现4就是我们需要的结果，但是这里还有个7，怎么办？再次 异或7；
有个小问题，7是什么？7是数组的长度
再比如：
0 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 等于 0
但是我们需要的结果是4，而4是什么？4就是数组长度
好了，现在我们回到练习题，练习题与现在顺序数组有什么区别呢??
对，区别就是顺序乱了！但是影响吗？不会，因为异或具有交换律
比如[0,4,1,2]
异或过程就是：0 ^ 0 ^ 1 ^ 4 ^ 2 ^ 1 ^ 3 ^ 2 ；
等价于： 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4
等于： 3 ^ 4
再给它异或长度4，就是我们求的3
代码示例：
int missingNumber(int* arr, int sz) { int ret = 0; int i = 0; for (i = 0; i < sz; i++) { ret = ret ^ i ^ arr[i]; } return ret ^ sz; } int main() { int arr[9] = { 9,6,4,2,3,5,7,0,1 }; int sz = sizeof(arr) / sizeof(arr[0]); int a = missingNumber(arr, sz); printf("缺少的是:%d ", a); return 0; }
运行结果：
练习题三
代码实现：求一个整数存储在内存中的二进制中1的个数
思路：计算机存储是补码，所以也就是求补码中有多少个1
5的补码为：00000101
4的补码为：00000100
把5和1相与，得到：00000100
所以5 & 4得到的结果就是：00000100，也就是4，抵消了数字5二进制的倒数第一个1
是不是明白了一点规律？
下面以数字251为例子
其实减1的作用就是为了让二进制最后一个1的后面全部为0，利于 相& 计算；
运用原理：n & (n-1)
代码示例：
int main() { int num = 0; scanf("%d", &num); int count = 0;//计数 while (num) { num = num & (num - 1); count++; } printf("二进制中1的个数 = %d\n", count); return 0; }
运行结果：
练习题四
输入一个整数n,判断n是不是2的次方.
是输出1,
否则输出0
输入:16
输出:1
输入:9
输出:0
输入:32
输出:1
原理还是：n & (n-1)
记得上面那个题我说的n-1的作用是什么吗?
把二进制中的最后一个1的后面全部变为0
8的补码：00001000 - 1 = 00000111
而2进制的每位的权重就是2的次方，比如1011换算成十进制 1x2³ + 0x2² + 1x2¹ + 1x2º = 11
所以2的次方的二进制只能有一个1，且在最高位，比如：
- 10000 (2的4次方 16)
- 100000(2的5次方 32)
那么只要 n & (n-1)的结果是0，就说明n是2的次方
代码示例：
int main() { int n = 0; scanf("%d", &n); int ret = 0; /* if语句表达式 if ((n & (n - 1)) == 0) { ret = 1; } else { ret = 0; } */ ret = (n & (n - 1)) == 0 ? 1 : 0; //运用的条件表达式,大家也可以用if判断 printf("%d\n", ret); return 0; }
运行结果：
练习题五
输入两个整数，求两个整数二进制中相同位置不同数字的位置有多少个?
输入: 22 33
输出: 5
输入:1999 2299
输出:7
解析:
题目要求的是：求相同位置不同数字的位置数量，那我们是不是可以把相同的数字全部转化为0??(用 ^ 或运算)
剩下的就是不同的数字了,然后就是消去 1
^或运算规则： 只要有1就是1，两个同时为0才为0
还是用 n & (n-1)
以22 33为例.，请看图：
而统计多少个1，不就是练习题一吗?
int main() { int n, m; scanf("%d %d", &n, &m); int ret = n ^ m; int count = 0; while (ret) { ret = ret & (ret - 1); count++; } printf("不同的位置有%d个", count); return 0; }
运行结果：
奇淫技巧一：n & 1
那么大家猜猜这个用来干嘛的？
对，判断整数n的奇偶性！
原理:
- 奇数的二进制末尾一定是1
- 偶数的二进制末尾一定是0
而1的二进制是00000000001等，前面全是0；
也就是说一个数与1进行**&运算**，实际运算的只有1位，那就是末位数字0或1（仔细去想想是不是）；
所以，如果n&1为真,就是奇数；否则偶数！
奇淫技巧二：n & (-n)
这个技巧我们是用来寻找该数字的最低位为1的某个二进制
比如有这样一个二进制数：1001101011100000
它的最低位1的位置在倒数第六个，即我们需要找下面这个数字：0000000000100000
就可以用上面的 n = n & (-n)技巧，最后n就是最低位的1
练习题六
n & (n-1)n & 1n & (-n) 技巧的综合练习
需要结合：& | ^运算技巧
