9999二进制 及 x=x&(x-1)问题
9999二进制 及 x=x&(x-1)问题
刘小米 发表于3年前
9999二进制 及 x=x&(x-1)问题
  • 发表于 3年前
  • 阅读 1236
  • 收藏 5
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

摘要: 深度剖析

题目:以下代码结果是多少?

# 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

 

 

看到这道题,结合后面的选项,我想,题目考察的肯定不是简单的计算问题,选项上面只有891011

这几种情况,于是,我就想,先把9999化成二进制的形式:1001 1100 0011 11,然后,将这个数值带

到上面的func()函数中,一步一步算,从后面的答案知道,题目最坏的情况是循环11次,也不多。所以,

经过漫长的计算,得出count的结果为8,这不正好是9999化成二进制中1的个数吗? 为什么经过x=x&(x-1)

之后,就能计算出该数的二进制中1的个数呢?百思不得其解,于是,求助百度。

 

从百度搜索的结果可知,x&(x-1)是把一个二进制数最右边的一个1变成0,例如,如果= 1011001,则:

x  =  1011001

1.    1011000

2.    1010000

3.    1000000

4.    0000000

x化成二进制中,有41,正好分成4步,count = 4,,但是问题还是没有解决,为什么这个式子会产生这个结果呢?

网上没有一个很确切的解答,大家似乎只知道这样做就行了!

从网上的资料我发现,这个公式来自《hacker's delight》这本书(中文版译作为《高效程序的奥秘》,从书中,我

还发现了很多这种很小的,也很变态的小式子:

 

1. 下面公式将一个字的最右侧的1位改为0位,如果没有1位则生成所有的位都为0的字(例如:0101 1000=>0101 0000)

                        x & (- 1)

2. 下面的公式可以用来检测一个无符号整数是否为2^- 1的形式(包括0和所有位均为1的情况)

                        x & (+ 1)

3. 使用下面的公式析出(isolate)最右侧的1位,如果没有1位则生成所有位均为0的字(如:0101 1000=>0000 1000)

                        x & (-x)

4. 使用下面的公式析出最右侧的0位,如果没有0位则生成所有位均为0的字(如:1010 0111=>0000 1000)

                        ~& (-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                                                    */

/*                                                                      */

/************************************************************************/

 

对于上面的124点,虽然不知道为什么这么做可以产生这个结果,但是我们可以举例子慢慢的推导,现在着重

看看第三点: x & (-x)

我们知道,在程序运行时,数据用的都是补码,对于整数运算 x&(-x),当x0时结果为0x为奇数时,结果为1

x为偶数时,结果为x2的最大次方的因子。

 

因为:&(-x) 就是整数x与其相反数(负号取反)的按位与:

& 1 = 1;

& 1 = 0;

& 0 = 1;

 

x0时,x&(-x)  0 & 0,结果为0

 

x不为0时,x-x必有一个为正。设x为正。

  ●x为奇数时,最后一个比特为1,取反加1没有进位,故x-x除最后一位外前面的位正好相反,按位与结果为0

   最后一位都为1,故结果为1

  ●x为偶数,且为2m次方(m>0)时,x的二进制表示中只有一位是1(从右往左的第m+1位),其右边有m0,左

   边也都是0(个数由表示x的字节数决定),故x取反加1后,从右到左第有m0,第m+1位及其左边全是1。这样,x& (-x) 得到的就是x

  ●x为偶数,却不为2m次方的形式时,可以写作x= y * (2^k)。其中,y的最低位为1。实际上就是把x用一个奇数左移k位来表示。

   这时,x的二进制表示最右边有k0,从右往左第k+1位为1。当对x取反时,最右边的k0变成1,第k+1位变为0;再加1,最右边的k

   就又变成了0,第k+1位因为进位的关系变成了1。左边的位因为没有进位,正好和x原来对应的位上的值相反。二者按位与,得到:

   k+1位上为1,左边右边都为0。结果为2^k,即x中包含的2的最大次方的因子。

 

总结一下:

    x&(-x),当x0时结果为0x为奇数时,结果为1x为偶数时,结果为x2的最大次方的因子。 比如x=32,其中2的最大次方因子为

    2^5,故x&(-x)结果为32;当x=28,其中2的最大次方因子为4,故& (-x)结果为4。当x=24,其中2的最大次方因子为8, x&(-x)结果为8

 

虽然,我们没能解决刚刚的根本问题,但是理解了& (-x)这个小的公式,知道怎么用了!C语言不光指针很强大,位运算也博大精深,

对于上面的公式,大家知道怎么用,分别用在哪些地方,作用是什么就行了!至于原理,如果哪位大神有自己的见解,希望与大家一起分享!

 

下面的例程是检测一个数是2n次方:

 

#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));

}


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 55
博文 57
码字总数 40921
评论 (0)
×
刘小米
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: