算法笔试模拟题精解之“一的个数”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第68题：一的个数 的题目解析，具体如下：

题目描述

题目等级：容易

知识点：位运算、贪心

查看题目：一的个数

给你两个数字l、r，问在区间[l,r]内的所有数中，二进制表示下“1”的个数最多的一个数是多少，如果有多个相同的，输出所有符合条件的数中最小的一个数。

输入一个整数l,和一个整数r。(1<=l<=r<=10^9)

输出一个数字表示[l,r]内二进制下“1”的个数最多的数。如果有多个，输出符合条件的数中最小的。

示例1

输入：

5

10

输出：

7

解题思路：二进制

根据题意，本题的所有数字应从二进制角度考虑。

所求数字可分为两部分，高位部分和低位部分，高位部分的值等于l, r高位相等的部分，在区间[l,r]中的所有数的高位部分都应该与其相等，即

high = r & (-1<<count)

，其中 count 为

l^r

的二进制的位数。

低位的部分计算过程如下：

如果 r-high 的值的二进制全为1，则低位部分为 r-high。如果不是全为1，则低位部分为

( 1<<(count-1) ) - 1

时间复杂度：O(log_2 n)

空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>