不含101的數(shù)
題目描述
小明在學(xué)習(xí)二進制時，發(fā)現(xiàn)了一類不含
101
101
101 的數(shù)，
也就是將數(shù)字用二進制表示，不能出現(xiàn)
101
101
101 。
現(xiàn)在給定一個正整數(shù)區(qū)間
[
l
,
r
]
[l,r]
[l,r]，請問這個區(qū)間內(nèi)包含了多少個不含
101
101
101 的數(shù)？
輸入描述
輸入一行，包含兩個正整數(shù) l , r ( 1 ≤ l < r ≤ 1 0 9 ) l,r (1 \leq l < r \leq 10^9) l,r(1≤l<r≤109) 。
輸出描述
輸出一行包含一個整數(shù)，表示在 [ l , r ] [l,r] [l,r] 區(qū)間內(nèi)一共有多少個不含 101 101 101 的數(shù)。
示例一
輸入
1 10
輸出
8
說明
區(qū)間[1,10]內(nèi)，5的二進制表示為101,10的二進制表達式為1010,因此出了5與10不滿足條件外，其他數(shù)字都滿足條件，因此答案為8。
示例二
輸入
10 20
輸出
7
說明
區(qū)間[10,20]內(nèi)，滿足條件的數(shù)字有[12,14,15,16,17,18,19]，因此答案為7。文章來源：http://www.zghlxwxcb.cn/news/detail-448758.html
思路
數(shù)字n最低三位為101，即n ^ 5（n異或5等于0），
將每個數(shù)字逐位右移并異或運算即可檢測是否存在二進制101。文章來源地址http://www.zghlxwxcb.cn/news/detail-448758.html
參考解題 Java
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
*
* @Author: Amos
* @E-mail: amos@amoscloud.com
* @Date: 2022/12/31
* @Time: 8:35
* @Description:
*/
public class Main0178 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int l = scanner.nextInt();
int r = scanner.nextInt();
int res = solution(l, r);
System.out.println(res);
}
}
private static final int x = 0b0111_1111_1111_1111_1111_1111_1111_1000;
private static int solution(int l, int r) {
int count = 0;
for (int i = l; i <= r; i++) {
int n = i;
while (n >= 5) {
if (((x | n) - x ^ 5) == 0) {
count++;
break;
}
n >>= 1;
}
}
return r - l + 1 - count;
}
}
到了這里，關(guān)于華為OD機試真題Java_2022-2023-題目0178-不含101的數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
