一道看似简单的面试题

kid143 发布于2019-07-01 10:21 / 894人阅读

摘要：二进制本身就是为这个数字而使用的，所以说这道面试题直指二进制的使用是没错的。正负在二进制中，第一位为的是负数，是正数。

前言

使用PHP,给定一个数,判断这个数是否是二的N次方

这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答这道题。先亮出答案

function exponentiation($number)
{
    if ($number < 0) {
        return false;
    }
        
    if (($number & ($number - 1)) == 0) {
        return true;
    } else {
        return false;
    }
}
    
exponentiation (2);
exponentiation (8);
exponentiation (16);
exponentiation (32);
exponentiation (128);

这是查阅后的最最标准的答案，其他类似通过循环等等答案就略过把。

运算

实际这道面试题考的并非是算法，而是作为开发人员的你“底子”够不够。
运算符应该是每门语言hello world 后立马要学习的。运算符分很多种，赋值运算符，比较运算符等等。我想大多自学或者培训出道的没有经过系统化学习的童鞋的，对这块的知识应该很薄弱把。当然赋值、比较什么的很熟悉，因业务基本逃不过这些。但对位运算符，你真的吃透了吗？

这道题的考点一是位运算符的使用，上面说过了本题考察的并非算法，而是你对二进制的了解，而在php中能操作二进制的运算符貌似 (我的知识范围内) 只有位运算符

PHP位运算符 (部分)

本道面试题用到了 & 所以不详解其他的运算符，需要更多了解请移步官方
http://php.net/manual/zh/lang...

运算符	附加信息
&	按位与运算符
^	按位异或运算符

按位与

按位与以简单易懂的方式来讲就是二进制位不相同的抵消，相同的保留

举几个栗子

公式 -> 转为二进制后的公式 -> 二进制结果 -> 十进制结果

2 & 3 -> 0010 & 0011 -> 0010 = 2
10 & 7 -> 1010 & 0111 -> 0010 = 2
32 & 70 -> 0100000 & 1000110 -> 0000000 = 0

按位异或

按位异或以简单易懂的方式来讲就是二进制位相同的抵消，不相同的保留

举几个栗子

公式 -> 转为二进制后的公式 -> 二进制结果 -> 十进制结果

2 ^ 3 -> 0010 ^ 0011 -> 0001 = 1
10 ^ 7 -> 1010 ^ 0111 -> 1101 = 13
32 ^ 70 -> 0100000 ^ 1000110 -> 1100110 = 102

进制

借用百度百科上的一段话

二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。它的基数为2，进位规则是“逢二进一”，借位规则是“借一当二”。

二进制本身就是为2这个数字而使用的，所以说这道面试题直指二进制的使用是没错的。2的n次方则就是

n	公式	结果
1	2	2
2	2x2	4
3	2x2x2	8
4	2x2x2x2	16

换算成二进制的表格是

n	公式	结果
1	2	000010
2	2x2	000100
3	2x2x2	001000
4	2x2x2x2	010000

由此看出2的n次方的二进制最高位是1，其余补0，(n&(n-1))==0 并且 n> 0 的情况下必定是2的n次方，为什么要-1呢？在二进制中每一位必须都不相同&后才会得出0，上述已经讲解了&的运算结果。例如十进制的16

16 & (16 - 1) = 
010000 & (001111) = 0

不要纠结(n&(n-1))==0 这个公式是怎么来的，作为程序员，我感觉应该把更多时间放到反推上面来，去应证这个公式的正确性。

验证是否是2的n次方，笨的方法就是一直除2，除到最后等于0则就是2的次方，所以公式如上

补位

如果是2个二进制进行运算时，计算机会统一位数，例如

01
011
<------> 
001
011

计算机会将01自动补一位为001去方便运算。

正负

在二进制中，第一位为1的是负数，0是正数。如果没有补零的情况下

10000000000
01111111111

虽然计算后也是0，但它并不是2的n次方，因为第一组二进制是负数。

补充

由上述题补充的另外一道题

给定任意数，计算是2的几次方？

function power($number){
    if ($number < 0) {
        return false;
    }
    
    if (($number & ($number - 1)) == 0) {
        
        // 数学不好的,就看下面的方法
        // $number = decbin($number);
        // return (mb_strlen($number)-1);
        // 数学可以的就看下面的方法
        return floor(log($number,2));
    } else {
        return false;
    }
}

判断是否是2的n次方

如果是则将十进制数字转为二进制

计算总长度-1获取到是2的几次方,按照0的个数来计算

致谢

感谢你看到这里，我也是文中提起的没好好学基础的一名程序员，但当你看到我这篇文章后，希望你也可以提起精神，去重温下基础，对你未来的职业生涯会起作用的。本章内容纯属自己理解，如有出入，请大佬们监督批评，谢谢

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/29078.html

求职准备 - 收藏集 - 掘金

摘要：一基础接口的意义百度规范扩展回调抽象类的意义想不想通过一线互联网公司面试文档整理为电子书掘金简介谷歌求职记我花了八个月准备谷歌面试掘金原文链接翻译者【面试宝典】从对象深入分析 Java 中实例变量和类变量的区别 - 掘金原创文章，转载请务必保留原出处为：http://www.54tianzhisheng.cn/... , 欢迎访问我的站点，阅读更多有深度的文章。实例变量和类变量...

cuieney 2019-08-16 10:36 评论0 收藏0
程序语言

摘要：一面应该还问了其他内容，但是两次面试多线程面试问题和答案采访中，我们通常会遇到两个主题采集问题和多线程面试问题。多线程是关于并发和线程的。我们正在共享重要的多线程面试问题和答案。。 2016 年末，腾讯，百度，华为，搜狗和滴滴面试题汇总 2016 年未，腾讯，百度，华为，搜狗和滴滴面试题汇总【码农每日一题】Java 内部类(Part 2)相关面试题关注一下嘛，又不让你背锅！问：Ja...

mtunique 2019-08-15 13:53 评论0 收藏0
程序语言

摘要：一面应该还问了其他内容，但是两次面试多线程面试问题和答案采访中，我们通常会遇到两个主题采集问题和多线程面试问题。多线程是关于并发和线程的。我们正在共享重要的多线程面试问题和答案。。 2016 年末，腾讯，百度，华为，搜狗和滴滴面试题汇总 2016 年未，腾讯，百度，华为，搜狗和滴滴面试题汇总【码农每日一题】Java 内部类(Part 2)相关面试题关注一下嘛，又不让你背锅！问：Ja...

stefan 2019-08-26 11:31 评论0 收藏0
一道简单的面试题引发的思考

摘要：另一个问题，就是我下面要提及的作用域问题，我当时思考的时间太久了这是回忆中的面试题实际略有差异，不纠结了说一下脚本的运行结果引用错误中给出的错误提示。版权声明：此文首发于我的简书账号人生还有多少个二十年，转载请注明出处。此处有几百字唠叨：　　当天，我早早起床，跨越上百公里，高德导航，路人指点，跌跌撞撞到达招聘会现场，当时已是中午十二点半，吃了午餐（半瓶白开水），开始准备投递...

wpw 2019-08-22 10:49 评论0 收藏0
一道面试题

摘要：写在前面这道题是本人在面试一家公司时的一个简单的基础问题，公司就不透露了，算是国内很有名的公司，本人面试的只是实习岗位。写在前面这道题是本人在面试一家公司时的一个简单的基础问题，公司就不透露了，算是国内很有名的公司，本人面试的只是实习岗位。一些大的问题就不再说了，每个人遇到的可能都是不一样的，基本会围绕着我们平常所常用的东西来聊，下面就说一道小题：题目写出下面几个表达式的结果：...

sihai 2019-08-21 15:26 评论0 收藏0