---
title: "变成1"
created: 2025-11-28
tags:
  - 算法
---

# 变成1

## 题目 [变成1](https://www.acwing.com/problem/content/description/4001/)

![[image-82fb141b.png]]

## 思路分析

位数不超过10^6 说明是高精度问题

还是一样 用容器进行模拟

string读入 逆序存储

如何判断是奇数偶数 其实就是取出最低位（最右） 也就是容器里的第一个元素

判断它是0还是1

若为奇数 就得进行加法

对于二进制的高精度加法

实质与十进制一样 只要修改%10 /10 为%2 /2即可

![[image-5e49289d.png]]

在原本的模板基础上 发现第二个加数可以不要

因为只有第一次计算时为1 其他时候都为0 那我不妨将t初始化成1 直接省去第二个加数

然后发现 二进制的加1 实际上就是将后面的连续的1变成0 然后最后一个0变成1

也就是只有当t=1的时候才要进行翻转 当t=0时 前面的位数都可以保持不变

那不妨直接在原容器里面进行修改 而不是重新拷贝一份结果

那么就得到

```cpp
for(int i=0;i<q.size();i++)
{
      t+=q[i];
      q[i]=t%2;
      t/=2;
      if(!t)
            break;
}
```

当然 也存在进位的情况 当循环结束了 t若还存在 就得pushback一个1

若为偶数

就除以2

二进制的除以2其实就相当于10进制的除以10

当最后一位为0时 其实就是往右边划掉一位

那就是要把容器里的第一个元素pop掉

但是vector没有从前面删元素的操作

所以改用deque 使用它的pop\_front（）

当然别忘了在每次加1和删0的操作后进行计数

步骤模拟如下

![[image-85018a96.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

int n;
deque<int> q;
string s;

int main()
{
    cin>>s;
    for(int i=s.size()-1;i>=0;i--)
        q.push_back(s[i]-'0');
    int cnt=0;
    while(q.size()>1)
    {
        int lowbit=q.front();
        if(lowbit%2)
        {
            int t=1;
            for(int i=0;i<q.size();i++)
            {
                t+=q[i];
                q[i]=t%2;
                t/=2;
                if(!t)
                    break;
            }
            if(t)
                q.push_back(1);
            cnt++;
        }
        else
        {
            q.pop_front();
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}
```

## 同类题型

## 视频讲解


---
⬅️ [[a+b|a+b]] 🏠 [[00-刷题理模型]] ➡️ [[大数运算|大数运算]]