文档章节

快速判断一个数是否是2的幂次方,若是,并判断出来是多少次方!

心中的理想乡
 心中的理想乡
发布于 2017/04/22 00:25
字数 409
阅读 34
收藏 0

将2的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1,并且1后面跟了n个0; 因此问题可以转化为判断1后面是否跟了n个0就可以了。

        如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1;因此将原来的数与去减去1后的数字进行与运算后会发现为零。

       最快速的方法:

      (number & number - 1) == 0

      原因:因为2的N次方换算是二进制为10……0这样的形式(0除外)。与上自己-1的位数,这们得到结果为0。例如。8的二进制为1000;8-1=7,7的二进制为111。两者相与的结果为0。计算如下:
         1000
     & 0111
        -------
        0000

扩展:求一个数n的二进制中1的个数。
非常巧妙地利用了一个性质,n=n&(n-1) 能移除掉n的二进制中最右边的1的性质,循环移除,直到将1全部移除,这种方法将问题的复杂度降低到只和1的个数有关系。

扩展问题二:

A和B的二进制中有多少位不相同。这个问题可以分为两步,(1)将A和B异或得到C,即C=A^B,(2)计算C的二进制中有多少个1。

© 著作权归作者所有

共有 人打赏支持
心中的理想乡

心中的理想乡

粉丝 24
博文 79
码字总数 120530
作品 0
深圳
程序员
私信 提问
计算大于或等于正整数的2的幂次方数

最近在open GL绘图的时候,遇到需要计算大于或等于这个数的最小的2的幂次方数(next highest power of 2)。因为Texture在显卡上的尺寸为2的幂次方。 算法基本原理是将这个数的每一位都置为1,...

adgkns
2013/05/21
0
1
LeetCode算法题-Power Of Two(Java实现)

这是悦乐书的第194次更新,第200篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第56题(顺位题号是231)。给定一个整数,写一个函数来确定它是否是2的幂。例如: 输入:1 输出...

小川94
2018/12/07
0
0
LeetCode算法题-Power of Four(Java实现-六种解法)

这是悦乐书的第205次更新,第216篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第72题(顺位题号是342)。给定一个整数(带符号的32位),写一个函数来检查它是否为4的幂。例...

小川94
2018/12/18
0
0
如何判断一个数是不是2的整数次方

将2的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1,并且1后面跟了n个0;因此问题可以转化为判断1后面是否跟了n个0就可以了。 如果将这个数减去1后会发现,仅有的那...

990653058
2015/04/14
0
0
LeetCode算法题-Power Of Three(Java实现-七种解法)

这是悦乐书的第204次更新,第215篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第71题(顺位题号是326)。给定一个整数,写一个函数来确定它是否为3的幂。例如: 输入:27 输...

小川94
2018/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

想问一下C++里queue要怎么遍历

如题,想知道怎么遍历<queue>对象的元素? 貌似不能遍历。要么全部pop push一遍,要么换个容器呗。 queue是先进后出的数据类型,只能不断读top()然后再pop()掉。故意把遍历操作隐藏掉了,...

shzwork
昨天
2
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
2
0
学习笔记1-goland结构体(struct)

写在前面:若有侵权,请发邮件by.su@qq.com告知。 转载者告知:如果本文被转载,但凡涉及到侵权相关事宜,转载者需负责。请知悉! 本文永久更新地址:https://my.oschina.net/bysu/blog/3036...

不最醉不龟归
昨天
3
0
【转】go get命令使用socket代理

由于某些不可描述的原因,国内使用go get命令安装某些包的时候会超时导致失败,比如net包、sys包、tools包等。第一种解决办法就是自己从git上下载后添加链接到GOPATH中,比如: 1234...

yiduwangkai
昨天
6
0
从上往下打印出二叉树的每个节点,同层节点从左至右打印。

//第一种做法 public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList <Integer> li=new ArrayList<Integer>(); ArrayList <TreeN......

南桥北木
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部