文档章节

9999二进制 及 x=x&(x-1)问题

刘小米
 刘小米
发布于 2015/06/05 10:11
字数 1792
阅读 1251
收藏 5

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

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

}


本文转载自:http://blog.csdn.net/fancong5201314/article/details/19765833

共有 人打赏支持
刘小米
粉丝 57
博文 59
码字总数 41272
作品 0
西安
其他
据说只有程序员才能看懂的时钟,你看明白了吗?

最近发现一个关于程序员的“数学钟”,也就是非常流行的下面这幅图: 以前,只知道其中十一个点钟的分析;对于3点钟,一直没有思路。于是发了一条朋友圈,求助大神解释其中的3点钟。在刘梓溪...

王练
2017/08/13
2.8K
41
google面试题及我的算法(2)——0~n之间1的个数(完美版)

本博客(http://blog.csdn.net/livelylittlefish)贴出作者(三二一、小鱼)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Problem Consider a function which, for a given whole num...

晨曦之光
2012/03/09
1K
8
构建一个简单的WCF应用

买了《WCF技术剖析》,按着书本的例子进行操作,写下我的操作过程。 参考博客:http://www.cnblogs.com/artech/archive/2007/02/26/656901.html 步骤一 构建整个解决方案 步骤二 创建服务契约...

嗯哼9925
2017/12/04
0
0
数据结构复习笔记(5)

1,KMP算法 void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; if (x[i] =......

嗯哼9925
2017/12/28
0
0
Python中的数值类型

Python中的基本数据类型有数值类型、字符串型、列表、元组、字典、集合等。本章介绍数值类型。数值类型包括整型、布尔型、浮点型和复数类型。 3.1 整型 3.1.1 取值范围 和其他语言一样,Pyt...

勇敢的石头
2017/12/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MySQL 乱七八糟的可重复读隔离级别实现

MySQL 乱七八糟的可重复读隔离级别实现 摘要: 原文可阅读 http://www.iocoder.cn/Fight/MySQL-messy-implementation-of-repeatable-read-isolation-levels 「shimohq」欢迎转载,保留摘要,谢...

DemonsI
59分钟前
2
0
Spring源码阅读——2

在阅读源码之前,先了解下Spring的整体架构: 1、Spring的整体架构 1. Ioc(控制反转) Spring核心模块实现了Ioc的功能,它将类与类之间的依赖从代码中脱离出来,用配置的方式进行依赖关系描...

叶枫啦啦
今天
1
0
jQuery.post() 函数格式详解

jquery的Post方法$.post() $.post是jquery自带的一个方法,使用前需要引入jquery.js 语法:$.post(url,data,callback,type); url(必须):发送请求的地址,String类型 data(可选):发送给后台的...

森火
今天
0
0
referer是什么意思?

看看下面这个回答(打不开网页可以把网址复制到搜索栏): https://zhidao.baidu.com/question/577842068.html

杉下
今天
1
0
使用U盘安装CentOS-解决U盘找不到源

1. 使用UltraISO制作CentOS安装盘 如果需要安装带界面的系统,为保证安装顺利,可选择Everything版本的ISO制作安装盘。 2. 在BIOS中选择使用U盘安装 系统启动后,进入安装选择界面,其中有三...

Houor
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部