光棍指数

[编程题]光棍指数

热度指数：280 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

对于一个正整数，我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高，这个数就越孤单。那么问题来了，对于给定的[a,b]区间中。最孤单的数字是谁呢？
如果光棍指数相同，最孤单的就是最小的那个数。

输入描述:

第一行一个整数 T (1≤T≤10^4)，表示问题数。
接下来 T 行，每行两个整数 a,b (0≤a≤b≤2^31−1)。数据之间用一个空格分隔。

输出描述:

对于每个问题，输出一行 Case x: y，其中 x 是问题编号，从 1 开始，y 是答案

示例1

输入

2
0 14
100 1000

输出

Case 1: 7
Case 2: 511

算法知识视频讲解

Java

墨竹mo

package 位运算;

/*
 * 
链接：https://www.nowcoder.com/questionTerminal/0e28cf34d05d422ea4a8fee8b4772c4a?orderByHotValue=1&page=1&onlyReference=false
来源：牛客网

对于一个正整数，我们认为它的光棍指数是它二进制表示下1的个数。
通常认为光棍指数越高，这个数就越孤单。那么问题来了，对于给定的[a,b]区间中。最孤单的数字是谁呢？
如果光棍指数相同，最孤单的就是最小的那个数。

解题思路：
看一下数字规模，穷举每个数求其二进制表示中1的个数，显然会超时。
可以这样想，既然要求"1"最多的数，那么我就对一个数从低位开始，将其低位上的0不断换成1，比较换之后的结果是否在区间内就行了。
关键：result |= result + 1;
 */
import java.util.Scanner;

public class 光棍指数 {    public static void main(String[] args) {    Scanner sc = new Scanner(System.in);    int T = sc.nextInt();    for (int i = 1; i <= T; i++) {    long a = sc.nextLong();    long b = sc.nextLong();    long result = a;    while ((result | (result + 1)) <= b) {    result |= result + 1;    }    System.out.println("Case " + i + ": " + result);    }    }
}