专栏首页Grace development一道看似简单的面试题

一道看似简单的面试题

前言

使用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/language.operators.bitwise.php

运算符

附加信息

&

按位与运算符

^

按位异或运算符

按位与

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

举几个栗子

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

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

2×2

4

3

2x2x2

8

4

2x2x2x2

16

换算成二进制的表格是

n

公式

结果

1

2

000010

2

2×2

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;
    }
}
  1. 判断是否是2的n次方
  2. 如果是则将十进制数字转为二进制
  3. 计算总长度-1获取到是2的几次方,按照0的个数来计算

致谢

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

最后修改:2个月前 2018-07-21

© 著作权归作者所有

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP To Go 转型手记 (一)

    作为一名PHP程序员,我感到荣幸。但在时代不断的变迁中,要具备足够的知识才可生存。

    CrazyCodes
  • Docker构建程序员的日常

    抛开Docker那些强大的功能,今天我们来部署下本地的开发环境。并写上几个脚本来提高开发效率。

    CrazyCodes
  • 微信支付-支付结果通用通知

    所有数据通过自己的逻辑保存后需要告诉微信一声,这时候需要再将代码组成xml发送给微信,微信给定了固定格式和字段

    CrazyCodes
  • Swift解读专题三——基础运算符 原

            运算符是编程语言不可缺少的一个部分,Swift中除了支持C中的运算符外,还提供了一些更加强大的运算符功能,例如取余符%可以用来计算浮点数,另外新...

    珲少
  • jsp中的JSTL与EL表达式用法及区别(一)

    对于JSTL和EL之间的关系,这个问题对于初学JSP的朋友来说,估计是个问题,下面来详细介绍一下JSTL和EL表达式他们之间的关系,以及JSTL和EL一些相关概...

    java达人
  • sql注入分类

    是一种结构化的查询语言,用于与数据库进行交互并能够被数据库解析。SQL注入攻击是一种常见的注入攻击类型。攻击方式在用户与程序进行交互时发生的。如在表单输入、搜索...

    cn0sec
  • Spring消息之STOMP

    JMCui
  • SpringBoot拦截器中无法注入bean的解决方法

    用户2409797
  • QApplication file not found

    青木
  • 案例解读宜信如何运用区块链双链技术重构供应链金融服务

    近日,银保监会下发了《中国银保监会办公厅关于推动供应链金融服务实体经济的指导意见》(以下简称“《意见》”),该《意见》提出,鼓励银行保险机构将物联网、区块链等新...

    宜信技术学院

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动