不申请临时变量的整数交换
private static void swap(int a, int b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
关于这样做行之有效的原因
先来解释b 为什么会变成 a。
首先，异或运算是符合交换律和结合律的，就是说 a ^ b ^ c 等于 a ^ c ^ b 等于 (a ^ b) ^ c。
所以，第二条语句就可以等价为 : b = a ^ b ^ b; ，因为（b ^ b） = 0 ,所以 b = a ^ 0 = a。
再来解释 a 为什么会变成 b。
结合以上说法，当运行到 第三行代码时，a = a ^ b 而 b = a,所以 a = a ^ b = a ^ b ^ a。
同上，结合异或运算的交换律， a = (a ^ a) ^ b = b。
其实，只要是互逆运算就可以进行这种不用临时变量的交换运算，如 加减法，乘除法。
public static void swap(int a,int b)
{
a = a + b;
b = a - b;
a = a - b;
}
public static void swap(int a,int b)
{
a = a * b;
b = a / b;
a = a / b;
}
不使用 + 来计算整数的加法（写加法器）
public static int plus(int a, int b)
{
while (b != 0)
{
int _a = a ^ b;
int _b = (a & b) << 1;
a = _a;
b = _b;
}
return a;
}
关于这样做行之有效的原因
主要利用异或运算来完成，异或运算有一个别名叫做：不进位加法。
那么a ^ b就是a和b相加之后，该进位的地方不进位的结果，相信这一点大家没有疑问，但是需要注意的是，这个加法是在二进制下完成的加法。
然后下面考虑哪些地方要进位？
什么地方需要进位呢？ 自然是a和b里都是1的地方
a & b就是a和b里都是1的那些位置，那么这些位置左边都应该有一个进位1，a & b << 1 就是进位的数值(a & b的结果所有左移一位)。
那么我们把不进位的结果和进位的结果加起来，就是实际中a + b的和。
a + b = (a ^ b) + (a & b << 1)
令:
a' = a ^ b, b' = (a & b) << 1 => a + b = (a ^ b) + (a & b << 1) = a' + b'
然后反复迭代，这个过程是在二进制下模拟加法的运算过程，进位不可能一直持续，所以b最终会变为0，也就是没有需要进位的了，因此重复做上述操作就可以 最终求得a + b的值。
用 O(1) 时间检测整数 n 是否是 2 的幂次
N如果是2的幂次，则N满足两个条件。
N > 0
N的二进制表示中只有一个1, 注意只能有1个。
因为N的二进制表示中只有一个1，所以使用N & (N - 1)将N唯一的一个1消去，应该返回0。
bool checkPowerOf2(int n)
{
return n > 0 && (n & (n - 1)) == 0;
}
x & (x - 1）的妙用
x & (x - 1)消去x最后一位的1。
计算在一个 32 位的整数的二进制表式中有多少个 1
由x & (x - 1)消去x最后一位的1可知。不断使用 x & (x - 1) 消去x最后一位的1，计算总共消去了多少次即可。
public int countOnes(int num)
{
int count = 0;
while (num != 0) // 不能是 > 0,因为要考虑负数
{
num = num & (num - 1);
count++;
}
return count;
}
如果要将整数A转换为B，需要改变多少个bit位？
这个应用是上面一个应用的拓展
思考将整数A转换为B，如果A和B在第i（0 <=i < 32）个位上相等，则不需要改变这个BIT位，如果在第i位上不相等，则需要改变这个BIT位。
所以问题转化为了A和B有多少个BIT位不相同！
联想到位运算有一个异或操作，相同为0，相异为1，所以问题转变成了计算A异或B之后这个数中1的个数!
public int countOnes(int num)
{
int count = 0;
while (num != 0) // 不能是 > 0,因为要考虑负数
{
num = num & (num - 1);
count++;
}
return count;
}
public int bitSwapRequired(int a, int b)
{
return countOnes(a ^ b);
}
应用：给定一个含不同整数的集合，返回其所有的子集
思路就是使用一个正整数二进制表示的第i位是1还是0来代表集合的第i个数取或者不取。 所以从0到2^n-1总共2^n个整数，正好对应集合的2^n个子集。如下是就是 整数 <=> 二进制 <=> 对应集合 之间的转换关系。
public List<List<Integer>> bitSubsets(int[] nums)
{
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < (1 << n); ++i) {
List<Integer> subset = new ArrayList<>();
for (int j = 0; j < n; j++) {
if((1 << j & i) != 0) {
subset.add(nums[j]);
}
}
list.add(subset);
}
return list;
}
巧用异或运算
应用一：数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数，因为相同的数出现的两次，异或两次等价于没有任何操作！
public int singleNumber(int[] nums)
{
int result = 0, n = nums.length;
for (int i = 0; i < n; i++)
{
result ^= nums[i];
}
return result;
}
应用二：数组中，只有一个数出现一次，剩下都出现三次，找出出现一次的数
因为其他数是出现三次的，也就是说，对于每一个二进制位，如果只出现一次的数在该二进制位为1，那么这个二进制位在全部数字中出现次数无法被3整除。
对于每一位，我们让Two，One表示当前位的状态。
我们看Two和One里面的每一位的定义，对于ith(表示第i位)：
如果Two里面ith是1，则ith当前为止出现1的次数模3的结果是2
如果One里面ith是1，则ith目前为止出现1的次数模3的结果是1
注意Two和One里面不可能ith同时为1，因为这样就是3次，每出现3次我们就可以抹去（消去）。那么最后One里面存储的就是每一位模3是1的那些位，综合起来One也就是最后我们要的结果。
如果B表示输入数字的对应位，Two+和One+表示更新后的状态
那么新来的一个数B，此时跟原来出现1次的位做一个异或运算，&上~Two的结果(也就是不是出现2次的)，那么剩余的就是当前状态是1的结果。
同理Two ^ B （2次加1次是3次，也就是Two里面ith是1，B里面ith也是1，那么ith应该是出现了3次，此时就可以消去，设置为0），我们相当于会消去出现3次的位。
但是Two ^ B也可能是ith上Two是0，B的ith是1，这样Two里面就混入了模3是1的那些位！！！怎么办？我们得消去这些！我们只需要保留不是出现模3余1的那些位ith，而One是恰好保留了那些模3余1次数的位，`取反不就是不是模3余1的那些位ith么？最终对(~One+)取一个&即可。
public int singleNumber(int[] nums)
{
int ones = 0, twos = 0;
for(int i = 0; i < nums.length; i++)
{
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}
应用三：数组中，只有两个数出现一次，剩下都出现两次，找出出现一次的这两个数
有了第一题的基本的思路，我们可以将数组分成两个部分，每个部分里只有一个元素出现一次，其余元素都出现两次。那么使用这种方法就可以找出这两个元素了。不妨假设出现一个的两个元素是x，y，那么最终所有的元素异或的结果就是等价于++res = x^y++。
++并且res！=0++
为什么呢？ 如果res 等于0，则说明x和y相等了！！！！
因为res不等于0，那么我们可以一定可以找出res二进制表示中的某一位是1。
对于x和y，一定是其中一个这一位是1，另一个这一位不是1！！！细细琢磨， 因为如果都是0或者都是1，怎么可能异或出1
对于原来的数组，我们可以根据这个位置是不是1就可以将数组分成两个部分。++x，y一定在不同的两个子集中。++
而且对于其他成对出现的元素，要么都在x所在的那个集合，要么在y所在的那个集合。对于这两个集合我们分别求出单个出现的x 和 单个出现的y即可。
public int[] singleNumber(int[] nums)
{
//用于记录，区分“两个”数组
int diff = 0;
for(int i = 0; i < nums.length; i ++)
{
diff ^= nums[i];
}
//取最后一位1
//先介绍一下原码，反码和补码
//原码，就是其二进制表示（注意，有一位符号位）
//反码，正数的反码就是原码，负数的反码是符号位不变，其余位取反
//补码，正数的补码就是原码，负数的补码是反码+1
//在机器中都是采用补码形式存
//diff & (-diff)就是取diff的最后一位1的位置
diff &= -diff;
int[] rets = {0, 0};
for(int i = 0; i < nums.length; i ++)
{
//分属两个“不同”的数组
if ((nums[i] & diff) == 0)
{
rets[0] ^= nums[i];
}
else
{
rets[1] ^= nums[i];
}
}
return rets;
}
最后
位运算的妙用到这就告一段落了，以上内容有一大部分是来自 九章算法位运算入门教程 ， 在 LintCode 上还有相应的编程练习，去练习一下会获得更好的效果。