这里写目录标题
一、常(装)见(逼)的位操作先看几个有意思的位操作：1、判断奇数偶数2、交换两个数字3、找出没有重复的数字4、m的n次方5、判断一个数是不是二的指数6、找出不大于N的最大2的幂指数二、leetcode解题136.只出现一次的数字(简单)191.位1的个数(简单)看完本文，可以顺便解决leetcode以下两个题目：
136.只出现一次的数字(简单)
191.位1的个数(简单)
一、常(装)见(逼)的位操作
先看几个有意思的位操作：
或操作|和空格将英文字符转换为小写，小写本身还是小写
(‘a’ | ’ ') = ‘a’
(‘A’ | ’ ') = ‘a’
与操作&和下划线将英文字符转换为大写，大写本身还是大写
(‘b’ & ‘’) = ‘B’
(‘B’ & '’) = ‘B’
n&(n-1) 消除数字 n 的二进制表示中的最后一个 1
异或^和空格进行英文字符大小写互换;判断异号
(‘d’ ^ ’ ') = ‘D’
(‘D’ ^ ’ ') = ‘d’
x^y < 0;异号，否则同号
下面我们从简单开始，一步一步的实现复杂的位运算~
1、判断奇数偶数
看到这个，你肯定觉得很简单，然后随手写下：
if (n % 2 == 0){// 偶数} else {// 奇数}
其实使用位运算，可以这样写
if ( n & 1 == 1){// 奇数} else {// 偶数}
因为如果一个二进制表示偶数的话
偶数的最后一位肯定是0；
奇数的最后一位肯定是1；
2、交换两个数字
这个也是很常见的操作，很简单的就可以写下来：
temp = x;x = y;y = temp;
但是如果在实际工作中，遇到不借助辅助空间，依旧让你去交换两个数字呢？
这个时候，位运算的优势就体现出来了
位运算实现如下：
x = x^yy = x^yx = x^y
看的第一眼，肯定很懵~ 啥玩意儿这是
首先，我们需要知道两个个基础的公式：
n^n =0; 即相同的两个数异或结果是0
n^0 = n;一个数和0异或的结果是本身
所以，上面展开一下，就是
x = x^yy = x^y^y = x^0 = xx = x^y = x^y^x = x^x^y = 0^y = y
3、找出没有重复的数字
我们以上面的为基础，即相同的两个数异或结果是0；一个数和0异或的结果是本身
那我们就把这一些数字，遍历一遍，全部异或一下，不就OK了？
4、m的n次方
要求一个数m的n次方，但是不能使用POW函数，如何做？
不要使用 m x m x m x m x m~ 一直乘以n次，太low了；
时间复杂度就是 O(n)
使用阶乘，复杂度可以降低到O(log N)
int pow(int n){int sum = 1;int tmp = m;while(n != 0){if(n & 1 == 1){sum *= tmp;}tmp *= tmp;n = n >> 1;}return sum;}
上述代码要是不理解二进制可能你就看不懂，这里我来举例解释一下
比如，求m的 5次方
我们把5用二进制表示，就是 0101，
从右往左看，第一个1 代表一个m
第二个1代表一个m x m x m x m ;
当二进制的这一位有1的时候，才把该位置代表的累乘的数算上，否则不算，继续看下一位的情况；
5、判断一个数是不是二的指数
如果一个数，是二的指数，那么它的二进制表示，肯定只有一个1
结合上面说到的：n&(n-1) 消除数字 n 的二进制表示中的最后一个 1
问题就好解决了
return (n > 0 ) && (n & (n - 1) == 0) ) ;
6、找出不大于N的最大2的幂指数
假设这个数是 19；
19用二进制表示就是 00010011
我们需要的结果就是 16 ；00010000
也就是 把 0010011，只保留最左边的一个1；
这个思路很简单，就是把最左边的1后面位，全部变成1；然后整体加1；由于加1之后会进位，所以在整体右移一位
应该怎么最左边的1后面位，全部变成1呢？
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 1;
结果是最左边的1和其右边，也会有一个1；11
n |= n >> 2;
结果是最左边的11和其右边，也会有一个11；1111
n |= n >> 4;
结果是最左边的1111和其右边，也会有一个11；11111111
如此这样，后面就都变成1了，然后+1，右移一位就行
二、leetcode解题
136.只出现一次的数字(简单)
这个题刚刚上面说过了，全部都异或
直接上答案；
class Solution {public:int singleNumber(vector<int>& nums) {//异或int n=nums.size();int res=0;for(int i=0;i<n;i++){res^=nums[i];}return res;}};
191.位1的个数(简单)
思路：
只需要记得：
n&(n-1) 消除数字 n 的二进制表示中的最后一个 1
class Solution {public:int hammingWeight(uint32_t n) {int res = 0;while (n != 0) {n = n & (n - 1);res++;} return res;}};
