专栏首页源懒由码求一个数的临近的较大的2的整数次幂

求一个数的临近的较大的2的整数次幂

被面试官问了这么一道题..........一问,想到,左移就好了。

就会很自然的写下这种方法

unsigned int f2(unsigned int val)
{
    int retval = 1;

    while (retval < val)
    {
        retval <<= 1;
    }

    return retval;
}

在改进一下,就判断他是不是2的次方先。如果是的话,可以直接返回。就可以得到这种方法。面试官又说,不能用循环递归,函数库。这下麻烦了。

unsigned int f1(unsigned int val)
{
    if (val & (val - 1))//至少有两个为1的bit位
    {
        unsigned int leftmost;

        while (val)
        {
            leftmost = val;
            val &= (val - 1);
        }

        return leftmost << 1;
    }
    else
    {
        return val == 0 ? 1 : val;
    }
}

想想,如果一个数,00101 如果能找到 00100的话就好了,这样在左移一位就完事了,但是想得时候就想要求地00100的话,不就要循环了。然后就卡住了。

接着看到这个 http://blog.codingnow.com/2011/12/buddy_memory_allocation.html

就得知,还可以这么写....溜到不行。把这个数,从高位数,第一个1的右边填满,再加1...溜溜溜溜的。

unsigned int f3(unsigned int val){
    {
        if (val & (val - 1)){
            val |= val>>1;
            val |= val>>2;
            val |= val>>4;
            val |= val>>8;
            val |= val>>16;
            return val+1;
        }else{
            return val == 0 ? 1 : val;
        }
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python selenium chrome option参数摘抄

    python + selenium 实现快照 (保存整个网页为图片):https://www.cnblogs.com/shuaichao/p/13176915....

    forxtz
  • functional 和 bind 用法

    使用 functional 和 bind 就可以简单绑定类成员函数参数,且能指定对象。

    forxtz
  • python爬虫伪装请求头---fake-useragent

    在编写爬虫进行网页数据的时候,大多数情况下,需要在请求是增加请求头,下面介绍一个python下非常好用的伪装请求头的库:fake-useragent,具体使用说...

    forxtz
  • golang 常见变成问题01

    往 chan 中放数据时,如果缓冲区已经满那么将 block 以下方方式可以试探往 chan 放数据

    landv
  • spark过节监控告警系统实现

    马上要过年了,大部分公司这个时候都不会再去谋求开新业务,而大数据工匠们,想要过好年,就要保证过年期间自己对自己的应用了如执掌。一般公司都会有轮值人员,至少要有春...

    Spark学习技巧
  • spark求最受欢迎的老师的问题

    曼路
  • 【技术分享】随机森林分类

    Bagging采用自助采样法(bootstrap sampling)采样数据。给定包含m个样本的数据集,我们先随机取出一个样本放入采样集中,再把该样本放回初始...

    腾讯智能钛AI开发者
  • spark基础练习(未完)

    1、filter val rdd = sc.parallelize(List(1,2,3,4,5)) val mappedRDD = rdd.map(2*_) ...

    用户3003813
  • 使用AES进行文件加密算法

    Xiaolei123
  • Spark实现排序

    question: 用spark对数据进行排序,首先按照颜值的从高到低进行排序,如果颜值相等,在根据年龄的升序排序

    曼路

扫码关注云+社区

领取腾讯云代金券