142. O(1)时间检测2的幂次除以2统计1的位数n和n-1取且

和蔼的zhxing

发布于 2018-09-04 13:05:41

5760

发布于 2018-09-04 13:05:41

文章被收录于专栏：和蔼的张星的图像处理专栏和蔼的张星的图像处理专栏

用 O(1) 时间检测整数 n 是否是 2 的幂次。样例 n=4，返回 true; n=5，返回 false.

除以2

这个当然是很简单也最容易想到，int的话可能要除31次才能出来。

统计1的位数

这个也容易想到，如果是2的幂次的话肯定是正的，然后去统计1的个数，需要移位和取且操作，和上面的方法差不多。因为除2本来就可以通过移位操作完成。

bool checkPowerOf2(int n) {
        int num=0;
        for(int i=0;i<31;i++)
        {
            if((n>>i)&1==1)
            {
                num++;
            }
        }
        return num==1;
       // write your code here
    }

n和n-1取且

这个是以前检测有多少个1的时候用到的一种方法，那个时候有一个结论：n&n-1可以减少一位1,如果用这种方法，那代码是相当简单：也符合时间复杂度要求。

    bool checkPowerOf2(int n) {
        if(n<=0)
        return false;
     
        return !(n&(n-1));
       // write your code here
    }

还有复习一下计算机中数字的表达形式：

有符号数最高位做符号位，0为正，1为负。
正数就是按照正常的表示方法。
负数用补码表示，补码为反码加1，反码是除符号位外其他位逐位取反。
-0表示当前位数最小的那个数。
n位有符号数的表示范围： -2^n-- 2^(n-1)-1

原码的表示：

　　　　左边是符号位，正数为0，负数为1。其他位表示数值

　　　　【+10】原码 = 00001010

　　　　【-10】原码 = 10001010 

　　　　【+0】原码 = 00000000

　　　　【-0】原码 = 10000000

　　反码的表示：

　　　　正数的反码和原码相同，负数的反码由原码除了符号位的其余位取反（即0表1,1表0）

　　　　【+10】反码 = 00001010

　　　　【-10】反码 = 11110101

　　　　【+0】反码 = 00000000

　　　　【-0】反码 = 11111111

　　补码的表示：

　　　　正数的补码与原码相同，负数的补码由原码的反码加1得到

　　　　【+10】补码 = 00001010

　　　　【-10】补码 = 【-10】反码 + 1 = 11110101 + 1 = 11110110　

　　　　【+0】补码 = 00000000

　　　　【-0】补码 = 【-0】反码 + 1 = 11111111 + 1 = 【1】00000000（mod（256））

补码的意义：补码实际上是一种模运算，以时钟为例，时钟一圈是12个小时，即时钟的模为12。如果当前时刻是3点钟，在12个小时之后时刻变为15点，15在模12之后，依然是3点。再如，将3点的时针调慢一个小时，即调成2点，和将时针向前调整11个小时的效果是一样的。因此用3-1和（3+11）mod（12）的结果一样。补码在机器码中的运用主要是用加法元算代替减法运算。CPU的加法器简单效率高，因此不需要再专门实现减法器。

在8位字中，我们的模就是2的8次方，即256。例如：直接减法：01000000（64）— 00001010（10） = 00110110（54） 用补码代替减法：01000000（64）+（11110110）（246）= 00110110（54） 两种运算结果是一样的。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017.12.21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

int

登录后参与评论

0 条评论

热度