全部博文（86）
分类： C/C++
2015-08-05 19:15:00
题目：以下代码结果是多少？
# include <iostream>
using namespace std;
int func(int x)
{
int count = 0;
while(x)
{
count ++;
x=x&(x-1);
}
return count;
}
int main(int argc, char **args)
{
cout << func(9999) <<endl;
return 0;
}
A. 8 B. 9 C. 10 D. 11
看到这道题，结合后面的选项，我想，题目考察的肯定不是简单的计算问题，选项上面只有8，9，10和11
这几种情况，于是，我就想，先把9999化成二进制的形式：1001 1100 0011 11，然后，将这个数值带
到上面的func()函数中，一步一步算，从后面的答案知道，题目最坏的情况是循环11次，也不多。所以，
经过“漫长的计算”，得出count的结果为8，这不正好是9999化成二进制中1的个数吗? 为什么经过x=x&(x-1)
之后，就能计算出该数的二进制中1的个数呢？百思不得其解，于是，求助百度。
从百度搜索的结果可知，x&(x-1)是把一个二进制数最右边的一个1变成0，例如，如果x = 1011001，则：
x = 1011001
1. 1011000
2. 1010000
?093. 1000000
4. 0000000
x化成二进制中，有4个1，正好分成4步，count = 4,，但是问题还是没有解决，为什么这个式子会产生这个结果呢？
网上没有一个很确切的解答，大家似乎只知道这样做就行了！
从网上的资料我发现，这个公式来自《hacker's delight》这本书（中文版译作为《高效程序的奥秘》，从书中，我
还发现了很多这种很小的，也很“变态”的小式子：
1. 下面公式将一个字的最右侧的1位改为0位，如果没有1位则生成所有的位都为0的字(例如：0101 1000=>0101 0000)
x & (x - 1)
2. 下面的公式可以用来检测一个无符号整数是否为2^n - 1的形式(包括0和所有位均为1的情况)：
x & (x + 1)
3. 使用下面的公式析出(isolate)最右侧的1位，如果没有1位则生成所有位均为0的字(如：0101 1000=>0000 1000)：
x & (-x)
4. 使用下面的公式析出最右侧的0位，如果没有0位则生成所有位均为0的字(如：1010 0111=>0000 1000)：
~x & (-x)
等等，还有很多，这里就不一一列举了,网上有个大牛总结得很好：
/* 将一个字的最右侧的1位改成0
* 若无1则生成所有位都为0的字
* 例：01011000 -> 01010000
* 可用来检测一个无符号整数是否为2的幂（==0）
*/
#define RESET_RIGHTEST_ONE(x) ((x)&((x)-1))
/*
* 将一个字最右侧的0位后的1都置0
* 例：01111111 -> 00000000
* 可用来检测一个无符号整数是否是2^n-1的形式（==0）
*/
#define CLEAR_RIGHT_ONE(x) ((x)&((x)+1))
/* 将一个字最右侧的1位后的0都置1
* 例：01011000 -> 01011111
*/
#define SET_RIGHT_ZERO(x) ((x)|((x)-1))
/* 析出最右侧的1位
* 如果没有1位则生成所有位均为0的字
* 例：01011000 -> 00001000
*/
#define CHECKOUT_RIGHTEST_ONE(x) ((x)&(-x))
/*
* 析出最右侧的0位
* 如果没有1位则生成所有位均为0的字
* 例：10100111 -> 00001000
*/
#define CHECKOUT_RIGHTEST_ZERO(x) ((~x)&(x+1))
/*
* 构造识别后缀0的掩码
* 如果x=0则生成所有位为1的字
* 例：01011000 -> 00000111
*/
#define GET_RIGHT_ZERO_MASK(x) ((~x)&(x-1))
/************************************************************************/
/* 逻辑操作与算术运算的基本恒等式 */
/* */
/* 1. -x = ~x + 1 = ~(x - 1) */
/* 2. ~x = -x - 1 = */
/* 3. -~x = x + 1 = */
/* 4. ~-x = x - 1 = */
/* 5. x + y = x - ~y - 1 = (x | y) + (x & y) */
/* 6. x - y = x + ~y + 1 = (x & ~y) - (~x & y) */
/* 7. x XOR y = (x | y) - (x & y) = */
/* 8. x & ~y = (x | y) - y = x - (x & y) */
/* 9. ~(x - y) = y - x - 1 = ~x + y */
/* */
/************************************************************************/
/************************************************************************/
/* 交换寄存器 */
/* */
/* 1. 交换两个数： */
/* x = x + y x = x - y x = y - x */
/* y = x - y y = y + x y = y - x */
/* x = x - y x = y - x x = x + y */
/* 2. 交换两个整数相应字段（m为模板）： */
/* x = x XOR y */
/* y = y XOR (x & m) */
/* x = x XOR y */
/* */
/************************************************************************/
对于上面的1，2，4点，虽然不知道为什么这么做可以产生这个结果，但是我们可以举例子慢慢的推导，现在着重
看看第三点： x & (-x)
我们知道，在程序运行时，数据用的都是补码，对于整数运算 x&(-x)，当x为0时结果为0；x为奇数时，结果为1；
x为偶数时，结果为x中2的最大次方的因子。
因为：x &(-x) 就是整数x与其相反数（负号取反）的按位与：
1 & 1 = 1;
0 & 1 = 0;
0 & 0 = 1;
当x为0时，x&(-x) 即 0 & 0，结果为0；
当x不为0时，x和-x必有一个为正。设x为正。
●当x为奇数时，最后一个比特为1，取反加1没有进位，故x和-x除最后一位外前面的位正好相反，按位与结果为0。
最后一位都为1，故结果为1。
●当x为偶数，且为2的m次方（m>0）时，x的二进制表示中只有一位是1（从右往左的第m+1位），其右边有m0，左
边也都是0（个数由表示x的字节数决定），故x取反加1后，从右到左第有m个0，第m+1位及其左边全是1。这样，x& (-x) 得到的就是x。
●当x为偶数，却不为2的m次方的形式时，可以写作x= y * (2^k)。其中，y的最低位为1。实际上就是把x用一个奇数左移k位来表示。
这时，x的二进制表示最右边有k个0，从右往左第k+1位为1。当对x取反时，最右边的k位0变成1，第k+1位变为0；再加1，最右边的k位
就又变成了0，第k+1位因为进位的关系变成了1。左边的位因为没有进位，正好和x原来对应的位上的值相反。二者按位与，得到：
第k+1位上为1，左边右边都为0。结果为2^k，即x中包含的2的最大次方的因子。
总结一下：
x&(-x)，当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子。 比如x=32，其中2的最大次方因子为
2^5，故x&(-x)结果为32；当x=28，其中2的最大次方因子为4，故x & (-x)结果为4。当x=24，其中2的最大次方因子为8,故 x&(-x)结果为8。
虽然，我们没能解决刚刚的根本问题，但是理解了x & (-x)这个小的公式，知道怎么用了！C语言不光指针很强大，位运算也博大精深，
对于上面的公式，大家知道怎么用，分别用在哪些地方，作用是什么就行了！至于原理，如果哪位大神有自己的见解，希望与大家一起分享！
下面的例程是检测一个数是2的n次方：
#include <stdio.h>
int func(int x)
{
if( (x&(x-1)) == 0 )
return 1;
else
return 0;
}
int main()
{
int x = 8
printf("%d\n", func(x));
}
