常用的运算符共 6 种，分别为 与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ << ）和右移（ >> ）。 转载自oi_wiki

与、或、异或

取反

位运算的应用

乘 2 的非负整数次幂

int mulPowerOfTwo(int n, int m) { // 计算 n*(2^m) return n << m; }

除以 2 的非负整数次幂

int divPowerOfTwo(int n, int m) { // 计算 n/(2^m) return n >> m; }

判断一个数是不是 2 的非负整数次幂

bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

对 2 的非负整数次幂取模

int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

取绝对值

int Abs(int n) { return (n ^ (n >> 31)) - (n >> 31); /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1 若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1) 需要计算 n 和 -1 的补码，然后进行异或运算， 结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */ }

取两个数的最大/最小值

// 如果 a>=b,(a-b)>>31 为 0，否则为 -1 int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); } int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }

判断符号是否相同

bool isSameSign(int x, int y) { // 有 0 的情况例外 return (x ^ y) >= 0; }

获取一个数二进制的某一位

// 获取 a 的第 b 位，最低位编号为 0 int getBit(int a, int b) { return (a >> b) & 1; }

将一个数二进制的某一位设置为 1

// 将 a 的第 b 位设置为 1 ，最低位编号为 0 int setBit(int a, int b) { return a | (1 << b); }

将一个数二进制的某一位取反

// 将 a 的第 b 位取反 ，最低位编号为 0 int flapBit(int a, int b) { return a ^ (1 << b); }

表示集合

一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 {1, 3, 4, 8} ，可以表示成

而对应的位运算也就可以看作是对集合进行的操作。

例题

洛谷P5514 [MtOI2019]永夜的报应

题目背景 在这世上有一乡一林一竹亭，也有一主一仆一仇敌。

有人曾经想拍下他们的身影，却被可爱的兔子迷惑了心神。

那些迷途中的人啊，终究会消失在不灭的永夜中……

题目描述 蓬莱山 辉夜(Kaguya)手里有一堆数字。

辉夜手里有 n 个非负整数 ，由于辉夜去打 Gal Game 去了，她希望智慧的你来帮忙。

你需要将这些数分成若干组，满足 nn 个数中的每一个数都恰好被分到了一个组中，且每一组至少包含一个数。 定义一组数的权值为该组内所有数的异或和。请求出一种分组方案，使得分出的所有组数的权值之和最小，输出权值之和的最小值。

输入格式 输入的第一行包含一个正整数 n，表示给定的非负整数的数量。

接下来一行包含 n 个非负整数

输出格式 输出一行一个整数表示答案。

输入输出样例 输入 #1

3 1 2 5

输出 #1

6

输入 #2

6 9 18 36 25 9 32

输出 #2

15

---

思路：易得a^b<=a+b 异或实际上就是不进位的加法 本题要求分组并把这些数加起来，使得总和最小

分组越少，异或越多，总和也就越小，所以只要分1组就可以

#include<iostream> using namespace std; int n,t,ans; int main() { cin>>n; while(n--) { cin>>t; ans^=t; } cout<<ans; return 0; }