Algorithms_入门基础_如何使用最高效的方式来判断一个数是否是2的N次方

简介: Algorithms_入门基础_如何使用最高效的方式来判断一个数是否是2的N次方


Question

引入… 先看个阿里巴巴的面试题吧

如何使用最高效的方式来判断一个数是否是2的N次方? 先思考下哈

Answer 1.0

分析下:

2的N次方嘛 ,举个例子 2 4 8 16是 2的N次方, 6 , 10 不是2的N次方。

2的N次方 ====> 就可以看成 这个数是不是可以拆成 N个2相乘嘛

那根据这个思路的话 ,写个伪代码

while(n>1){
  n % 2 == 0  ---> 如果除以2不为0 ,肯定不是2的N次方 
  n = n / 2 ; ---> 继续除以2 (即我们上面说的拆成N个2),循环判断 
}

分析好了,我们来用Java语言实现下

/**
 * @author 小工匠
 * @version v1.0
 * @create 2019-11-19 21:22
 * @motto show me the code ,change the word
 * @blog https://artisan.blog.csdn.net/
 * @description
 **/
public class Test {
    /**
     * 思路:
     * 如果某个数除以2 不等于0 ,最起码已经不是2的倍数了,更不要是2的N次方了 ,
     * 比如  3 ,5 ,7这种数字
     * 利用该特性循环判断
     *
     * @param args
     */
    public static void main(String[] args) {
        int n = 6;// 原始数值
        int temp = n; // 临时变量
        while (temp > 1) {// while循环
            if (temp % 2 == 0) { // 判断是否是2的倍数
                temp = temp / 2; // 除以2 继续下一次的循环判断
                System.out.println(temp == 1 ? ("原始数值【" + n + "】是2的N次方") : ("分析中...." + temp));
            } else {// 不是2的倍数,肯定不是2的N次方了,直接break跳出循环
                System.out.println(n + "不是2的N次方");
                break;// 终止循环
            }
        }
    }
}

好了,算是实现了, 其实看看这个代码是比较挫的,有没有更好的思路呢 ?

提示一下: 按位与运算


Answer 2.0 按位与运算 &

为啥能想到这种思路,其实也是要靠积累的,对数字要有足够的敏感,看到某个十进制的数,可以马上想到对应的二进制数。

八位二进制嘛 ,为啥是8位,请移步下方的须知

我们来看下几个数字

2 ,4 ,8 ,16

我们来看下 2 ,4 ,8 ,16 这几个十进制的是 对应的 二进制 ,咋算的 请移步下方的须知

2 = 10        ---->补位凑成8位  -----> 00000010
4 = 100       ---->补位凑成8位  -----> 00000100
8= 1000       ---->补位凑成8位  -----> 00001000
16=10000      ---->补位凑成8位  -----> 00010000

接下来我们看下 比2 4 8 16 小1的十进制整数,对应的二进制

2 = 10            ---->补位凑成8位  -----> 00000010
1 = 01            ---->补位凑成8位  -----> 00000001
4 = 100           ---->补位凑成8位  -----> 00000100
3 = 011           ---->补位凑成8位  -----> 00000011
8 = 1000          ---->补位凑成8位  -----> 00001000
7 = 0111          ---->补位凑成8位  -----> 00000111 
16 = 10000        ---->补位凑成8位  -----> 00010000
15 = 01111        ---->补位凑成8位  -----> 00001111   

按二进制位进行“与”运算 ,只有两个数的二进制同时为1,结果才为1,否则为0。

我们看下上面的规律哈 n 和 n-1 这两个十进制的整数 ,按照二进制进行 按位与运算后,为0,那么这个n就是2的N次方。

伪代码如下

if((n & (n-1)) == 0)) -----> n 就是 2的次方

接下来我们用java实现以下

/**
 * @author 小工匠
 * @version v1.0
 * @create 2019-11-19 21:27
 * @motto show me the code ,change the word
 * @blog https://artisan.blog.csdn.net/
 * @description
 **/
public class TestA {
    /**
     * 思路:
     *      按位与运算 &  , 两个数字按照二进制的形式进行"与"运算 ,如果结果为0 ,则是2的N次方
     * @param args
     */
    public static void main(String[] args) {
        int  n = 128 ;
        System.out.println((n&(n-1)) == 0 ? n + "是2的N次方"  : n + "不是2的N次方");
    }
}

须知

十进制转二进制

十进制整数转换为二进制整数采用"除2取余,逆序排列"法。

具体做法:

用2整除十进制整数,可以得到一个商和余数;

再用2去除商,又会得到一个商和余数,如此进行,直到商为小于1时为止,

然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。

一图胜千言 ,来吧


八位二进制

我们常说 “八位二进制” ,到底是啥意思嘞 ?

说起二进制 ,其实就要从计算机的的组成-电子元件说起, 这些元件一般都是只有两种稳定的工作状态,用高、低两个电位表示“0”和“1”在物理上是最容易实现的。

那八位二进制又是什么妖魔鬼怪呢? 我们知道 电脑的最小存储单位是字节Byte ,即我们常说的大B, 一个字节, 是由八位二进制位组成的,就是这八位数字只是由“0”和“1”两个数字组成 ,比如 11111000,00000001,00000101等等。

八位二进制 就是一个字节(Byte)的大小。

1个英文字母、英文标点、半角数字 在计算机是以八位二进制数保存 就是一个字节大小,

1个汉字(包括中文标点 全角数字)就是2个字节 (十六位二进制)

1位二进制大小就是1bit ,就是我们说的 小b。


在计算机科学中,bit通常用于表示信息的最小单位,也可以被称作是二进制位。在计算机学科中,bit一般用0和1表示。Byte也就是人们常说的字节,通常由8个位(8bit)组成一个字节(1Byte)

比如我们常见的基本类型的取值范围

bit与Byte之间可以进行换算,具体的换算关系为:1Byte=8bit

在计算机网络或者是网络运营商中,一般而言,宽带速率的单位用bps(或b/s)表示;bps表示比特每秒即表示每秒钟传输多少位信息,是bit per second的缩写 小b 。 在实际所说的1M带宽的意思是1Mbps(是兆比特每秒Mbps不是兆字节每秒MBps)。

1B=8b 1B/s=8b/s(或1Bps=8bps)
1KB=1024B 1KB/s=1024B/s
1MB=1024KB 1MB/s=1024KB/s

规范提示:实际书写规范中B应表示Byte(字节),b应表示bit(比特),但在平时的实际书写中有的把bit和Byte都混写为b ,如把Mb/s和MB/s都混写为Mb/s,导致人们在实际计算中因单位的混淆而出错。切记注意!!!


按位与运算 &

定义: 参加运算的两个数,按二进制位进行“与”运算

运算规则:只有两个数的二进制同时为1,结果才为1,否则为0。

比如 0 & 0= 0 ,0 & 1= 0,1 & 0= 0, 1 & 1= 1。

举个例子 :

3 &5 即 00000011 & 00000101 = 00000001 ,所以 3 & 5的值为1。



相关文章
|
4月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
43 0
|
6月前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
7月前
|
算法 搜索推荐 Java
图计算中的PageRank算法是什么?请解释其作用和计算原理。
图计算中的PageRank算法是什么?请解释其作用和计算原理。
85 0
|
7月前
|
开发者 索引 Python
【python刷题】LeetCode 2057E 值相等的最小索引(5种简单高效的解法)
【python刷题】LeetCode 2057E 值相等的最小索引(5种简单高效的解法)
50 0
|
运维 监控 应用服务中间件
【运维知识高级篇】34道Shell编程练习题及答案(从基础到实战:基础+计算+判断+循环+控制与数组+实战进阶)(二)
【运维知识高级篇】34道Shell编程练习题及答案(从基础到实战:基础+计算+判断+循环+控制与数组+实战进阶)(二)
955 0
|
运维 Shell Linux
【运维知识高级篇】34道Shell编程练习题及答案(从基础到实战:基础+计算+判断+循环+控制与数组+实战进阶)(一)
【运维知识高级篇】34道Shell编程练习题及答案(从基础到实战:基础+计算+判断+循环+控制与数组+实战进阶)
698 0
|
存储 NoSQL API
【Redi设计与实现】第六章:整数集合
【Redi设计与实现】第六章:整数集合
【Redi设计与实现】第六章:整数集合
|
开发者
【解决方案 二十九】如何高效优雅的在word写公式
【解决方案 二十九】如何高效优雅的在word写公式
87 0
|
Java
java学习第五天笔记-循环高级和数组99-求和并统计个数
java学习第五天笔记-循环高级和数组99-求和并统计个数
79 0
java学习第五天笔记-循环高级和数组99-求和并统计个数
|
Python
Python经典编程习题100例:第88例:读取数字个数
Python经典编程习题100例:第88例:读取数字个数
84 0