目录

一.位运算详解

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）。

各种位运算的使用

  1. & 运算<mark>按位与运算符</mark>
    & 有0为0无0为1
    and 运算通常用于二进制取位操作， 例如一个数 and 1的结果就是取二进制的最末位。 这可以用来判断一个
    整数的奇偶， 二进制的最末位为 0 表示该数为偶数， 最末位为 1 表示该数为奇数.
  2. |运算 <mark>按位或运算符</mark>
    | 有1为1无1为0
    or 运算通常用于二进制特定位上的无条件赋值， 例如一个数 or 1 的结果就是把二进制最末位强行变成 1。
    如果需要把二进制最末位变成 0， 对这个数 or 1 之后再减一就可以了， 其实际意义就是把这个数强行变成最接
    近的偶数。
  3. ^ 运算<mark>异或运算符</mark>
    ^ 相同为0不同为1
    xor 运算通常用于对二进制的特定一位进行取反操作， 因为异或可以这样定义： 0 和 1 异或 0 都不变， 异或 1
    则取反。
  4. ~ 运算
    ~ 运算的定义是把内存中的0和 1 全部取反。 使用 ~ 运算时要格外小心， 你需要注意整数类型有没有符
    号。
  5. << 运算
    a << b就表示把a转为二进制后左移b位 （ 在后面添b个0）。
  6. >>运算
    和 << 相似， a >> b 表示二进制右移 b 位（ 去掉末 b 位）， 相当于 a 除以 2 的 b 次方（ 取整）。

分割线（上面全是粘的）

在使用位运算的时候，需要注意的一点是他的优先级

上面这个图是在别的博客里找到=。= 好难记。。。

其实只要记住这几点就差不多了：

1.取非比较快，仅次（） .

2.其余需要两个变量的位运算比算术运算（如+ - * / ）要低，比赋值运算（=），逻辑运算要高（||, &&）

3.左移右移比较调皮，跳到关系运算（> < <= == !=）上面

如果还是不好记。。那就括号大法好

位运算这么麻烦，为什么还要用他呢，因为他的速度特别快，可以用位运算来实现一些功能
比较常用的几个功能：

a乘以2除以2：<< >>

判断奇偶性：a&1，为零为偶，否则奇数

交换两个数：a^=b^=a^=b;(可以不借助别的变量）

判断两个数是否相同：a^b==0则相同，否则不同（可以快速从只有一个数出现一次其余都出现偶数次的一串数里找到这个数，1 1 2 3 3 3 3 4 4 ，从头异或一遍，就可以得到2）其实异或还有更大作用的用法，下面会提到
去掉二进制最后一个1:i-=i&-i,也可以写作i=i&（i-1），在树状数组里会用到

下面举几个简单基础的可能会用到位运算的常见算法和有趣的题:

二.位运算应用

1.快速幂

实用且简单，位运算则大大节省了时间（其实因为快速幂本身就很快，不选择位运算一般的题也能ac）
下面是代码：

#include<stdio.h>
int main()
{
	int n,a;
	scanf("%d %d",&n,&a);
	int t=n,ans=1;
	while(a)
	{
		if(a&1)
		ans*=t;
		t*=t;
		a>>=1;
	}
	printf("%d\n",ans);
	return 0;
}

像这些比较有名的算法，只说用法，就不说原理了，
还有快速幂延伸的矩阵快速幂。。。

2.给定一个数组A, 长度为n，求下面这段程序的值

ans = 0;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

ans ^= A[i] + A[j];

输入
多组测试数据，第一行一个整数T，T<=20,表示数据的组数，每组数据一行包含n, m, z, l; A[1] = 0; A[i] = (A[i-1] * m + z) mod l; 1 <= n, m, z, l <= 5 * 10^5
输出
每组数据输出Case #x: ans 其中x代表第几组测试数据，从1开始，ans代表程序中的ans.
样例输入1

2
3 5 5 7 
6 8 8 9

样例输出1

Case #1: 14
Case #2: 16

水题一秒思考分界线

这道题不是很难，但也挺有意思的，重点考察对异或的理解，直接模拟肯定是过不了的，
A[i] + A[j]=A[j] + A[i];所以除了主对角线上的项只异或了一遍外，其余都异或了两遍，异或两遍不就为零了，说以直接把主对角线上的乘二异或起来就好了

#include<stdio.h>
int main()
{
	long long int t,ans,sum,a;
	int n,m,i,z,l;
	scanf("%lld",&t);
	for(int j=1;j<=t;j++)
	{
		sum=0;
		ans=0;
		scanf("%d %d %d %d",&n,&m,&z,&l);
		a=0;
		for(i=1;i<n;i++)
		{
			a=(a*m+z)%l;
			ans^=(a*2);
		}
		printf("Case #%d: %lld\n",j,ans);
	 } 
 }

3.数数字

描述
给你一个整数数列，保证只有一个数出现过奇数次，输出它。
输入
多组测试数据。 每组测试数据第一行为一个整数n，代表该数列元素个数。（1 <= n <= 500000） 第二行为n个整数ai，以空格隔开。（-1000000 <= ai <= 1000000）
输出
输出一行表示这个出现奇数次的数。

样例输入1

5
2 3 2 3 1
7
6 6 6 2 6 6 6

样例输出1

1
2

这个题更水，懂上面那道题了，这个还不秒切？
全部异或起来就出答案了，因为异或符合交换律，而别的数异或0等于本身，出现偶数次的数会全部异或成0，奇数次的数自然也就出来了

#include<stdio.h>
int main()
{
	int a,b;
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%d",&a);
		for(int i=1;i<n;i++)
		{
			scanf("%d",&b);
			a^=b;
		}
		printf("%d\n",a);
	}
	return 0;
}

4.数数字 2

描述
输入一些数字，int范围内，大部分数字都出现了三次，只有一个数字出现了一次，输出这个数字。
输入
第一行是数字的个数n，n < 2000000，接下来每行一个数字。
输出
输出出现了一次的数字
样例输入1

4
1
1
1
3

样例输出1

3

这个要比上面的复杂一些，出现三次和出现一次，都是奇数次，异或起来好像没什么区别啊=。=看了半天，想了半天丝毫没有思路，没办法，只能搜题解了

走你☞

因为十进制的数字在计算机中是以二进制的形式存储的，所以数组中的任何一个数字都可以转化为类似101001101这样的形式，int类型占内存4个字节，也就是32位。那么，如果一个数字在数组中出现了三次，比如18，二进制是10010，所以第一位和第四位上的1，也都各出现了3次。

因此可以用ones代表只出现一次的数位，twos代表出现了两次的数位，xthrees代表出现了三次的数位。

 public int singleNumber(int[] A) {
        int ones=0;
        int twos=0;
        int xthrees=0;
        for(int i = 0;i <A.length;i++){
                twos ^= (ones&A[i]);
                ones ^= A[i];
                xthrees = ~(ones&twos);
                twos &= xthrees;
                ones &=xthrees;
         }
         return ones;
    }

不过说实话，我没怎么看懂。。。。不过后来从某飞君学到了一个更简单的做法，按位记录每一个数那个位的出现的次数，最后把这些位的次数对三取余，再转为十进制就是要求的数。虽然没有用到位运算，但这是一种按位去考虑的方法，值得一记。

#include<stdio.h>
#include<string.h>
int main()
{
	int dight[40],a,b=0;
	int n,i;
	memset(dight,0,sizeof(dight));
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&a);
		i=0;
		while(a)
		{
			dight[i++]+=a%2;
			a/=2;
		}
	}
	int t=1;
	for(i=0;i<32;i++)
	{
		dight[i]%=3;
		b+=dight[i]*t;
		t*=2;
	}
	printf("%d\n",b);
	return 0;
}

这个复杂度是nlogn，所以sort也能做，仅供参考

5.nim博弈问题：

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

对于一个Nim游戏的局面(a1,a2,…,an)，它是必赢状态当且仅当a1a2…an=0，其中表示异或(xor)运算。

题目链接：HDU 1849
Problem Description
大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去逛公园，不去和AC男约会，两个人竟然猫在寝食下棋……
说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的：
1、棋盘包含n个方格，方格从左到右分别编号为0，1，2，…，n-1；
2、m个棋子放在棋盘的方格上，方格可以为空，也可以放多于一个的棋子；
3、双方轮流走棋；
4、每一步可以选择任意一个棋子向左移动到任意的位置（可以多个棋子位于同一个方格），当然，任何棋子不能超出棋盘边界；
5、如果所有的棋子都位于最左边（即编号为0的位置），则游戏结束，并且规定最后走棋的一方为胜者。
对于本题，你不需要考虑n的大小（我们可以假设在初始状态，棋子总是位于棋盘的适当位置）。下面的示意图即为一个1*15的棋盘，共有6个棋子，其中，编号8的位置有两个棋子。

大家知道，虽然偶尔不够浪漫，但是Rabbit和Grass都是冰雪聪明的女生，如果每次都是Rabbit先走棋，请输出最后的结果。
Input
输入数据包含多组测试用例，每个测试用例占二行，首先一行包含一个整数m（0<=m<=1000），表示本测试用例的棋子数目，紧跟着的一行包含m个整数Ki(i=1…m; 0<=Ki<=1000)，分别表示m个棋子初始的位置，m=0则结束输入。
Output
如果Rabbit能赢的话，请输出“Rabbit Win!”，否则请输出“Grass Win!”，每个实例的输出占一行。
Sample Input

2 3 5 3 3 5 6 0

Sample Output

Rabbit Win! Grass Win!

#include<stdio.h>
int main()
{
	int ans,a,m;
	while(~scanf("%d",&m))
	{
		ans=0;
		if(m==0)
		break;
		while(m--)
		{
			scanf("%d",&a);
			ans^=a;
		}
		if(ans==0)
		printf("Grass Win!\n");
		else
		printf("Rabbit Win!\n");
	}
	return 0;
}

只介绍用法，至于为什么要用异或，可以搜nim博弈的相关博客

6.树状数组

树状数组是用于求区间和，同时支持单点更新

优点就是代码长度短，可以求解一些线段树的题

模板：

#include<stdio.h>
#define max_n 1000
int bit[max_n+1],n;
int sum(int x)
{
	int sum=0;
	while(x>0)
	{
		sum+=bit[x];
		x-=x&-x;
	}
	return sum;
}
void add(int x,int a)
{
	while(x<=n)
	{
		bit[x]+=a;
		x+=x&-x;
	}
	return ;
}
int main()
{
	int x,i,a;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		add(i,a);
	}
	scanf("%d",&x);
	printf("%d\n",sum(x));//前x个数的和
	scanf("%d",&a);
	add(x,a);//单点更新 
	printf("%d\n",sum(x)); 
	return 0;
 }

7.判断一个数x是不是2的某次方

x&（x-1）==0？YES : NO;

神殿

神殿
icebound通过勤工俭学，攒了一小笔钱，于是他决定出国旅游。这天，icebound走进了一个神秘的神殿。神殿由八位守护者守卫，总共由64个门组成，每一道门后都有一个迷宫，迷宫的大小均为100×100。icebound在迷宫中总共耗时T小时，消耗食物K公斤。历经千辛万苦之后，icebound终于穿越了迷宫，到达了神殿的中心。神殿的中心有一个宝箱。宝箱上显示有两个正整数ll和r。icebound苦思冥想，终于发现一些打开宝箱的线索。你需要找到一个数P，它具有一个美妙的性质：它是[l,r]中所有数的二进制表示里，1的个数最多的一个数。如果你发现了这个美妙的数字，你就可以打开宝箱，获得巨额财富。

比如[4,8]中：

4: 0100
5: 0101
6: 0110
7: 0111
8: 1000

二进制表示中1的个数最多的数是7，它含有3个1。

INPUT

输入一行，两个正整数：ll和rr，用空格隔开，代表神殿中宝箱上显示的数。
1<=T<=2^21,1<=K<=10^5,1<=l<r<=2*10^9

OUTPUT

一个十进制数P，代表满足条件的解。如果有多个P满足条件，输出最小的P。
测试样例

4 8

样例输出

7

题意理解：
就是给定一个区间，找区间中二进制一最多的那个数
多个答案取最小值
解题思路：
这道题要是硬做的话，我目前还没有想到比较好的解决方法，搜索？转字符串？排列组合？回溯？好像听上去都可以，但是好像都不太好写，而且复杂度高的不敢想。
但是这道题如果用位运算来做的话，几乎是一道签到题。
n|(n+1)一定会比n的二进制多一个一而且还是从低位向高位加一，保证n以内就可以找到1最多且最小的那个解。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long l,r;
    cin>>l>>r;
    while((l|(l+1))<=r){
        l|=(l+1);
    }
    cout<<l<<endl;
    return 0;
}

这件事告诉我们，签到题就在那里，就看你能不能用签到的方法做了。

对于这道题，我开始也没有想到这个方法，我的确想到二进制是不是在暗示我用位运算做，但是也的确没想到为什么要n|(n+1)看完巨佬的题解才发现，这个方法简直妙啊，于是我决定把这题当作案例记下来，下次好提醒自己遇到意思位运算多想想能不能写一些这样的公式出来。

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧