按位与运算符（&）

“a&b”是指将参加运算的两个整数a和b，按二进制位进行“与”运算。

运算规则：
0&0=0; 0&1=0; 1&0=0; 1&1=1; 即：两位同时为“1”，结果才为“1”，否则为0
例如：3&5 即 0000 0011& 0000 0101 = 0000 0001 因此，3&5的值得1。
另，负数按补码形式参加按位与运算。
**

被二整除、数中定位、清零

1、比如我们经常要用的是否被2整除，一般都写成 if(n % 2 ＝＝ 0) 可以换成 if((n&1) ＝＝ 0)

2、按位与运算可以取出一个数中指定位。
例如：要取出整数84从左边算起的第3、4、5、7、8位，只要执行84 & 59,因为84对应的二进制为01010100，59对应的二进制为00111011，01010100 & 00111011= 00010000 可知84从左边算起的第3、4、5、7、8位分别是0、1、0、0、0。

3、清零。如果想将一个单元清零，使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

整数幂

判断一个数n ，是不是2的整数幂。
比如：64＝2^6,所以输出“yes”,而65无法表示成2的整数幂的形式，所以输出“NO”。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {  int n;
  5.    cin>>n;
  6.    if(n&(n-1))cout<<"NO";
  7.    else cout<<"Yes";
  8. }

2的幂

image.png
对于一个数的二进制表示，如果这个数是2的幂，那么该数减1的结果是后面所有位为1，再与原数进行与运算结果必定为0.

  1. class Solution {
  2.     public boolean isPowerOfTwo(int n) {
  3.         if(n<=0) return false;
  4.         return (n&n-1)==0?true:false;
  5.     }
  6. }

4的幂

image.png
image.png
image.png

计算一个数的二进制中1的个数

算法1：通过与初始值为1的标志位进行与运算，判断最低位是否为1；然后将标志位左移，判断次低位是否为1；一直这样计算，直到将每一位都判断完毕。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {      int n = 0,num;
  5.     unsigned int flag = 1;
  6.     cin>>num;
  7.      while(flag)
  8.     {    if(num & flag) n++;
  9.         flag = flag << 1;
  10.     }
  11.     cout<<n;
  12. }

算法2：还有一种方法，一个整数减一，可以得到该整数的最右边的1变为0，这个1右边的0变为1。对这个整数和整数减一进行与运算。直到该整数变为0，进行的与运算的次数即为整数中1的个数。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {      int n = 0,num;
  5.     unsigned int flag = 1;
  6.     cin>>num;
  7.      while(num)
  8.     {    num = num & (num - 1);
  9.         n++;
  10.     }
  11.     cout<<n;
  12. }

颠倒二进制位

image.pngimage.png
image.png

  1. public class Solution {
  2.     // you need treat n as an unsigned value
  3.     public int reverseBits(int n) {
  4.         int res=0;
  5.         for(int i=0;i<32;++i){
  6.             res=res<<1;
  7.             res=n&1|res;
  8.             n=n>>1;
  9.         }
  10.         return res;
  11.     }
  12. }

数字范围按位与

image.png
image.png
image.pngimage.pngimage.png

  1. class Solution {
  2.     public int rangeBitwiseAnd(int m, int n) {
  3.         int shift = 0;
  4.         // 找到公共前缀
  5.         while (m < n) {
  6.             m >>= 1;
  7.             n >>= 1;
  8.             ++shift;
  9.         }
  10.         return m << shift;
  11.     }
  12. }

image.pngimage.pngimage.png

  1. class Solution {
  2.     public int rangeBitwiseAnd(int m, int n) {
  3.         while (m < n) {
  4.             // 抹去最右边的 1
  5.             n = n & (n - 1);
  6.         }
  7.         return n;
  8.     }
  9. }

按位或运算符（|）

参加运算的两个对象，按二进制位进行“或”运算。
运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；即 ：参加运算的两个对象只要有一个为1，其值为1。
例如:3|5　即 00000011 | 0000 0101 = 00000111 因此，3|5的值得7。　
另，负数按补码形式参加按位或运算。

存储多个布尔值

可以用一个unsigned int 来存储多个布尔值。
比如一个文件有读权限，写权限，执行权限。看起来要记录3个布尔值。我们可以用一个unsigned int也可以完成任务。
一个数r来表示读权限，它只更改个位来记录读权限的布尔值 00000001 (表示有读权限) 00000000 (表示没有读权限)
一个数w表示写权限，它只用二进制的倒数第二位来记录布尔值 00000010 (表示有写权限) 00000000 (表示没有写权限)
一个数x表示执行权限，它只用倒数第三位来记录布尔值 00000100 (表示有执行权限) 00000000 (表示没有执行权限)
那么一个文件同时没有3种权限就是 ~r | ~ w | ~ x 即为 00000000，就是0
只有读的权限就是 r | ~w | ~x 即为 00000001，就是1
只有写的权限就是 ~r | w | ~x 即为 00000010，就是2
一个文件同时有3种权限就是 r | w | x 即为 00000111，就是7

按位异或运算符（^）

参加运算的两个数据，按二进制位进行“异或”运算。运算规则：0 ^ 0=0； 0 ^ 1=1； 1^ 0=1； 1^1=0；即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

下面重点说一下按位异或,异或 其实就是不进位加法 , 如1+1=0，,0+0=0,1+0=1。
异或的几条性质:
1、交换律:a ^ b = b ^ a
2、结合律:(a ^ b) ^ c = a^ (b ^ c)

“异或运算”的特殊作用：
（1）使特定位翻转: 例：X=10101110，使X低4位翻转，用X ^ 0000 1111 = 1010 0001即可得到。
（2）与0相异或，保留原值 ，10101110^ 00000000 = 1010 1110。
（3）对于任何数x都有――自反性:x^ x=0，x^ 0=x 例如：A^B ^ B = A
（4）交换二个数：a =a ^ b; b = b ^ a; a = a ^ b;

只出现一次数字

给出 n 个整数，n 为奇数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。
【输入样例】
9
3 3 7 2 4 2 5 5 4
【输出样例】
7

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {   int i,n,m,a;
  5.     cin>>n;
  6.     cin>>a;
  7.     for(int i = 2; i <= n; i++) {
  8.         cin>>m; 
  9.         a^=m;
  10.     }
  11.     cout<<a<<endl;
  12. }

找唯一重复值

1~1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

解法一、显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去1+2+…+1000的和。这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。

解法二、异或就没有这个问题，并且性能更好。将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {  int i,n,a[11]={1,2,5,3,4,5,6,7,8,9,10};
  5.    n=a[0]^a[1];
  6.   for(i=2;i<=10;i++)n=n^a[i]; 
  7.   for(i=1;i<=10;i++)n=n^i;
  8.   cout<<n;
  9. }

找唯二不重复数

一系列数中,除两个数外其他数字都出现过两次,求这两个数字,并且按照从小到大的顺序输出.例如 2 2 1 1 3 4.最后输出的就是3 和4
image.png
算法
**
先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
在异或结果中找到任意为 1 的位。
根据这一位对所有的数字进行分组。
在每个组内进行异或操作，得到两个数字。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[1000];
  4. int main()
  5. {       int n;
  6.         scanf("%d", &n);
  7.         int x = 0;
  8.         for(int i = 1; i <= n; i++) {      scanf("%d", &a[i]); x ^= a[i];    }
  9.         int num1 = 0, num2 = 0;
  10.         int tmp = 1;
  11.         while(!(tmp & x)) tmp <<= 1;
  12.         cout<<tmp<<endl;
  13.         for(int i = 1; i <= n; i++) {
  14.             if(tmp & a[i]) num1 ^= a[i];
  15.             else num2 ^= a[i];
  16.         }
  17.         printf("%d %d\n", min(num1, num2), max(num1, num2));
  18.     return 0;
  19. }
  1. class Solution {
  2.     public int[] singleNumber(int[] nums) {
  3.         int result[] = new int[2];
  4.         int mid = 0 , index = 1;
  5.         for (int num : nums) {
  6.             mid ^= num;
  7.         }
  8.         while ((index & mid)==0) index <<= 1;
  9.         for (int num : nums) {
  10.             if ((num & index)!=0) result[0] ^= num;
  11.             else result[1] ^= num;
  12.         }
  13.         return result;
  14.     }
  15. }

数组内三次中找一次

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int ones = 0, twos = 0;
  4.         for(int num : nums){
  5.             ones = ones ^ num & ~twos;
  6.             twos = twos ^ num & ~ones;
  7.         }
  8.         return ones;
  9.     }
  10. }

image.pngimage.png

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int[] counts = new int[32];
  4.         for(int num : nums) {
  5.             for(int j = 0; j < 32; j++) {
  6.                 counts[j] += num & 1;
  7.                 num >>>= 1;
  8.             }
  9.         }
  10.         int res = 0, m = 3;
  11.         for(int i = 0; i < 32; i++) {
  12.             res <<= 1;
  13.             res |= counts[31 - i] % m;
  14.         }
  15.         return res;
  16.     }
  17. }

丢失的数字

image.png
image.png

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         int missing = nums.length;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             missing ^= i ^ nums[i];
  6.         }
  7.         return missing;
  8.     }
  9. }

两数之和

image.png
image.png

按位取反运算符（~）

按位取反运算符（~）是指将整数的各个二进制位都取反，即1变为0，0变为1。

例如，~9＝－10，因为9（00001001）所有位取反即为（11110110），这个数最高位是1，所以是补码。补码还原成反码（反码等于补码减1）得到（11110101），再还原为原码（反码到原码最高位不变，其它各位取反）等于（10001010）， 十进制为－10。

按位左移运算符（<<）

左移运算符是用来将一个数的各二进制位左移若干位，移动的位数由右操作数指定（右操作数必须是非负值），其右边空出的位用0填补，高位左移溢出则舍弃该高位。

在高位没有1的情况下，左移1位相当于该数乘以2，左移2位相当于该数乘以2*2＝4,15＜＜2=60，即乘了４。
但此结论只适用于该数左移时被溢出舍弃的高位中不包含1的情况。

例如：143<<2 结果为60 因为143转换为进制为10001111，左移2得00111100 ，结果为60。

按位右移运算符（>>）

右移运算符是用来将一个数的各二进制位右移若干位，移动的位数由右操作数指定（右操作数必须是非负值），移到右端的低位被舍弃，对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。
注意：对无符号数,右移时左边高位移入0；对于有符号的值,如果原来符号位为0(该数为正),则左边也是移入0。
如果符号位原来为1(即负数),则左边移入0还是1,要取决于所用的计算机系统。有的系统移入0,有的

系统移入1。移入0的称为“逻辑移位”,即简单移位；移入1的称为“算术移位”。
例： a的值是八进制数113755：
a:1001011111101101 （用二进制形式表示）
a>>1: 0100101111110110 (逻辑右移时)
a>>1: 1100101111110110 (算术右移时)
在有些系统中,a>>1得八进制数045766,而在另一些系统上可能得到的是145766。Turbo C和其他一些C

编译采用的是算术右移,即对有符号数右移时,如果符号位原来为1，左面移入高位的是1。
源代码：
#include
main()
{ int a=0113755; printf(“%d”,a>>1);}

复合赋值运算符

位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：

1、&= 例：a &=b 相当于a=a& b
2、|= 例：a |=b 相当于a=a |b
3、>>= 例：a >>=b 相当于a=a>> b
4、<<= 例：a<<=b 相当于a=a<< b
5、^= 例：a ^= b 相当 a=a ^b

运算规则：和前面讲的复合赋值运算符的运算规则相似。

不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时，系统会将二者按右端对齐，然后进行位运算。

以“与”运算为例说明如下：如果一个4个字节的数据与一个2个字节数据进行“与”运算，右端对齐后，左边不足的位依下面三种情况补足：

（1）如果整型数据为正数，左边补16个0。

（2）如果整型数据为负数，左边补16个1。

（3）如果整形数据为无符号数，左边也补16个0。

常见的二进制位的变换操作

image.png