---
title: "进制"
created: 2025-11-28
tags:
  - 算法
---

# 进制

## 题目 [进制](https://www.acwing.com/problem/content/description/4985/)

![[image-f7e172bc.png]]

## 思路分析

反向枚举

比如111 三位中 只有一位为0的数只有 110 101 011三个（其实011不行 无前导0）

也就是说 可以在固定的位数中 枚举每个0出现的位置

得到的数 如果在ab区间中 那就++

然后这里 数据范围是$10^{18} $那么最多也就$2^{60}$

![[image-c117fb5a.png]]

![[image-909ab5d8.png]]

![[image-bb002215.png]]

最多有60位

枚举这60位 把第i位变成0

显然首先要把所有位置成1 之前学过

1<<60 得到1后跟60个0

减去1 那就是60个1

这样就得到了一个全是1的序列

怎么把第i位变成0呢

那就要生成一个100……的掩码（1<<j)

去与全1序列做异或（相同得0） 或者做减法也行

这样就可以得到修改后的res

若这个res在ab范围内 就cnt++

当然只是最多有60位 这个60也得枚举 可能一共1位 2位……60位

再分别对这些情况 去做上述操作 把0放在每一位（最高位其实不行 要求不能有前导零）

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL a,b;

int main()

{

    cin>>a>>b;

    int cnt=0;

    //最多60位 最少1位 遍历所有情况

    for(int i=1;i<=60;i++)

    {

        //对于每一种情况 从0位开始尝试把每一位设为0

        //因为不能有前导零（0不能放在最高位）所以最高能放的位置应该是i-1

        //但是因为外层循环是从1开始的 内层循环是从0开始的 所以还得减去个1

        //所以范围为[0,i-2]

        for(int j=0;j<=i-1-1;j++)

        {

            //构造成i位全1的序列 异或或者减去一个第j位为1的掩码

            //即可得到一个答案 把它转为10进制看 看他是否在ab范围内

            LL res=(1ll<<i)-1 ^ (1ll<<j);

            //LL res=(1ll<<i)-1 - (1ll<<j);

            if(res>=a && res<=b)

                cnt++;

        }

    }

    cout<<cnt<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[数组中唯一只出现一次的数字|数组中唯一只出现一次的数字]] 🏠 [[00-刷题理模型]] ➡️ [[位运算相关问题|位运算相关问题]]