第13章 位运算

⼏种常见的位运算1、判断奇偶数如果把⼀个数n以⼆进制数的形式表⽰的话，我们只需要判断最后⼀个⼆进制位是1还是0即可。

如果是1，则代表奇数，否则为偶数。

代码如下：if(n & 1 == 1){// n是奇数}2、交换两个数x = x ^ y; // (1)y = x ^ y; // (2)x = x ^ y; // (3)我们都知道两个相同的数异或之后的结果为0，即 n ^ n = 0，并且任何数与0异或之后等于它本⾝，即 n ^ 0 = n。

于是我们把（1）中的x代⼊（2）中的x，有：y = x ^ y = (x ^ y) ^ y = x ^ ( y ^ y) = x ^ 0 = x，这样x的值就赋给了y。

对于（3），推导如下：x = x ^ y = (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y，这样y的值就赋给了x。

异或运算⽀持运算的交换律和结合律。

3、找出没有重复的数给你⼀组整型数据，这些数据中，其中有⼀个数只出现了⼀次，其他的数都出现了两次，让你来找出⼀个数这道题可能很多⼈会⽤⼀个哈希表来存储，每次存储的时候，记录下某个数出现的次数，最后遍历哈希表找出只出现了⼀次的次数。

这种⽅式的时间复杂度是O(n)，空间复杂度也为O(n)了。

其实这道题也可以进⾏位运算，，我们可以把这⼀组整型数全都异或，由于两个相同的数异或的结果为0，⼀个数与0异或的结果为其⾃⾝，所以异或的所得到的结果就为只出现了⼀次的数。

例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。

其中 5 只出现了⼀次，其他都出现了两次，把他们全部异或⼀下，结果如下：1 ^2 ^3 ^4 ^5 ^ 1 ^ 2 ^ 3 ^ 4 = （1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 0 ^ 0 ^ 5 = 5代码如下：int find(int[] nums){int tmp = nums[0];for(int i = 1;i < nums.length; i++)tmp ^= arr[i];return tmp;}4、2的n次⽅求解 2 的 n 次⽅，并且不能使⽤系统⾃带的 pow 函数很多⼈看到这个题可能觉得让n个2相乘就⾏了，如果这么做的话，时间复杂度为O（n)了。

2020/12/09
11
11.9 位段 有时存储一个信息不必用一个或多个字节，可以在
一个字节中存放几个信息。例如, “真”或“假”用1或 0 表示，只需要 1 位就够了。
一、 在一个字节中存放几个数据
图中：a、b、c、d分别占2位、6位、4位、4位。假定c 原来的值为0，现要变为12，则：
将数 12 左移 4 位，使 1100 成为右边起第 4~7 位。
10
main( )
{unsigned a,b,c; int n;
scanf(“a=%o,n=%d”,&a,&n);
b = a<<(16–n);
c = a>>n;
c = c¦b;
printf(“%o\n%o\n”,a,c);
}
运行情况：
a=157653, n=3
157653 75765
(11011)2 10101)2
11.6 “左移”运算符 << << 用来将一个数的各二进制位全部左移若干位，并在 右边补若干个0。高位左移后溢出，舍弃不起作用。如：
<< 运算的最大用途是做乘法运算。将乘以2n的幂运算
处理202为0/12/左09 移 n 位。
6
11.7 “右移”运算符 >>
>>用来将一个数的各二进制位全部右移若干位，移 到右边的低位被舍弃，对无符号数，高位补0。
二、 位段 位段是以位为单位定义长度的结构体类型中的成员。
struct packed_data { unsigned a: 2;
unsigned b: 6; unsigned c: 4; unsigned d: 4; int i; }data; 结构体中 2020/12/09 a、b、c、d 共占 2 个字节，i 占2个字节1。3

12.2 位 段
#include<stdio.h> int main() {
struct cbit {
unsigned a:1; unsigned b:3; unsigned c:4; } bit, *pbit; bit.a = 1; bit.b = 7; bit.c = 15; printf("%d,%d,%d\n", bit.a, bit.b, bit.c); pbit = &bit;
相关概念
(1) 位段的定义与结构体的定义相仿;格式如下: struct 位段结构名 { 类型说明符1 位段名1:位段长度1; //最低位; 类型说明符2 位段名2:位段长度2; //次低位; 类型说明符3 位段名3:位段长度3; ...... 类型说明符N 位段名N:位段长度M; //最高位; };
return 0;
}
12.1.1 按位与运算符（&）
实例分析 设a=84（二进制为01010100），把其中从左边算起的 第3，4，5，7，8位保留下来。
12.1.2 “按位或”运算符（｜）
基本形式 或运算的基本格式为：a | b
12.1.2 按位或运算符（｜）
#include <stdio.h>
12.1.4 取反运算符（~）
#include <stdio.h> int main() {
int a=077; printf("%d"，~a); return 0; }
程序运行结果如下： 192
12.1.5 左移运算符（<<）
基本形式
左移运算的基本格式为： a<<n
功能：左移运算符是用来将一个数的各二进制位左 移若干位，移动的位数由右操作数指定（右操作数必须 是非负值），其右边空出的位用0填补，高位左移溢出 则舍弃该高位。

内存地址
字节（byte）
0x0012FF7C 0x0012FF7B 0x0012FF7A
10100100 00010101 01101110
尽管位运算操作的是位，也得基于字节这个整体。 位运算通常是用于无符号整型操作数的运算。
4
基本位操作符
❖~ 按位取反
高
❖<< 左移
❖ >> 右移
❖ & 按位与
❖^ 按位异或
20
宏定义好处
1.提高了可读性：数字本身并没有什么实际的意义。 例如： #define PI 3.1415926
2.减少了书写错误：我们用#define 定义个常量 PI代表 3.1415926, 用宏定义后， 只要一处校验，其它相同的错误 也解决了。
3.维护性：有时我们需要将某个特定数据，在程序中出现 的所有实例加以修改，我们只做一个改动就达到目的。 #define MAXSIZE 100
(&) 10: 0000 1010
结果: 0000 1000
5.按位或运算 |
12: 0000 1100 (|) 10: 0000 1010
结果: 0000 1110
9
基本位操作符
&用途： 用屏蔽字“与”变量可以取出变量的某些位： 例如 a 00101100 10101100 b 00000000 11111111 那么 a &b 00000000 10101100 这里b被称为“位掩码”，作用如同筛子。 注意：位掩码应与所操作的值相同长度。
00 0 1 101 1
12
基本位操作符
^ 位异或用途： 可以使变量某个特定的位翻转
例如
a 00101100 10101100 b 11111111 00000000