首先感谢Nibnat的提醒，昨天最后一个检查2的幂的例子写错了，正确的方法应该是
return ( Number & ( Number - 1 )) ==0;
这个问题在二进制表示下比较好理解，2的次幂在二进制下的特点很明显：只有一个bit是1，其他bit都是0，于是任务转换成怎么检查一个二进制数是由一个’1’和好多个’0’组成的。理解上面的运算，需要把注意力放在Number中所有值为’1’的bit的最低位上（我们称它为最低’1’bit位）。根据定义，最低’1’bit位左边可能是0-1组成的任意序列，右边只能是若干个0组成的序列。2的幂和非2的幂的区别是非2幂的最低’1’bit左边一定有至少一个’1’bit,而2幂的最低’1’bit位左边全是0。
现在看看上面的运算做了什么事情，Number-1之后，最低’1’bit位的值由1变成0，原来最低’1’bit位左边的序列保持不变，右边的0序列变成1序列。跟Number按位进行与运算之后，Number最低’1’bit位右边的序列保持不变，最低’1’bit位及其左边的序列全变成0.于是最终结果相当于检查Number的最低’1’bit位左边还有没有别的’1’bit了。
0是特殊情况，按照数学定义，0不是2的幂，不过上面的方法会输出TRUE，需要用别的方法检查一下。
既然提到最低’1’bit位这个概念了，今天就趁这个机会介绍另一个与之相关的，我特别喜欢的例子。直接上代码先：
x;
y = x & -x;
c = x + y;
x = (((x ^ c) >> 2) / y) | c;
这个例子比较复杂，容我一步一步解开大家心里的疑问。
问题一：y是什么？
需要先说明一下，计算机中使用补码来存储负数，所谓补码，就是按位取反之后再加1，所以-x其实相当于~x+1。x按位取反之后，原来最低’1’bit位变成了0，右边全变成1了。加1就如同推到了第一块多米诺骨牌一样，从最右边开始把一串1又变回了0，骨牌效应到最低’1’bit这里停止，把它从0又拽回来变成1了。总结一下，-x相当于只把最低’1’bit左边内容变反，和x按位与运算之后，最低’1’bit为1，其他地方全部是0。所以y其实是x的最低’1’bit。
问题二：c是什么？
前面解释过了，y其实是x的最低’1’bit，那么x和自己的最低’1’bit位相加结果是什么呢？还是用多米诺骨牌来解释这个过程。把x中的1想象成多米诺骨牌，0想象成空地，加1就相当于推到一个骨牌，只要下一位还是1，那么就会一直向高位进位，直到遇到一个0的时候才会停止进位。x可以理解为被0隔开的一段段连续的1，c就是把x最右端的一片1推到后再来一次进位的结果。
问题三：x^ c是什么？
异或运算的规则是二者不同则结果为真，那我们来看看x和c在哪些bit上会取不同的值。依然把x理解为被0隔开的一段段连续的1，c是把x最右端的一片1推到成0之后的结果，那么可以确定x和c不一样的地方，就是x最右端的那一串连续的1，所以x ^ c的结果其实就是x最右端的一串1外加一次进位。
((x ^ c) >> 2)比较好理解，就是右移两位。
问题四：除y做什么？
前面第一个分析过，y是x的最低’1’bit。y只有这一个1，其他地方都是0，所以y是2的幂！计算机中除以2的幂，等价于右移运算。于是((x^ c) >> 2)|y的作用相当于把x^ c右移了2+log（y）bit，实际是把x最右端的一串1使劲地往右移动，直到把一个1都挤出去了。
问题五：为什么要和c按位或？
第二个问题中分析了c是把x最右端的一串1推到变成0，然后向前进一位的结果，而((x ^ c) >> 2) / y是x最右端的一串1使劲地往右移动直到挤出去一位的结果，他俩按位或运算，就是把x最右端的一串1分成两个部分，第一个bit往前进一位，其余的被压到最右端去。
整个过程解释完了。
问题六：这段代码到底在干啥？
把x理解成若干个1和0组成的二进制字符串，从问题五的答案总可以看出，这段代码并没有改变字符1的个数，而是把最右端的一串连续的1的位置调整了一下。仔细想想可以发现，这是在保证1的个数不变的前提下，下一个最小的x。这个功能在组合问题中使用的特别多，可以帮我们找到所有从m个元素中选出n个元素的方案。
这段代码是计算机界的大牛，Hacker界的鼻祖BillGosper发现的，因此也被称为G函数。我们最后用几个例子来展示一下其中的微妙
网友评论