在C ++中将二进制表示形式的数量减少为1的步骤数
假设我们有一个二进制形式的数字s。我们必须找到在这些规则下将其减少到1的步骤数-
如果当前数字是偶数，我们必须将其除以2。
如果当前数字为奇数，则必须对其加1。
因此，如果输入类似于“1101”，则输出将为6，因为“1101”为13。因此，13为奇数，加1并获得14。然后14为偶数，除以2并获得7。那7是奇数，加1并得到8。
然后8再一次是偶数除以2得到4。再一次4是偶数除以2得到2，最后2是偶数除以2得到1。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数addStrings()，它将使用一个数组num1，一个数组num2，
定义数组ret
进位：=0，总和：=0
反转num1和num2
i：=0，j：=0
而（i<num1的大小或j<num2的大小），做-
和：=进位+（num2[j]）
在sum的末尾插入summod2
进位：=sum/2
（将j增加1）
总和：=进位+（num1[i]）
在sum的末尾插入summod2
进位：=sum/2
（将i增加1）
sum：=进位+（num1[i]+num2[j]）
在sum的末尾插入summod2
进位：=sum/2
（将i增加1）
（将j增加1）
如果i<num1的大小和j<num2的大小，则-
否则，当i<num1的大小时，则-
除此以外
如果进位不为零，则-
在ret结尾处插入进位
i：=ret的大小
ans：=空字符串
对于i>=0，更新（将i减1），-
ans：=ans+（ret[i]+ASCII'0'）
返回（如果ans的大小等于0，则为“0”，否则为ans）
定义一个函数addBinary()，它将使用一个数组a，一个数组b，
返回addStrings(a,b)
定义一个数组makeVector并从v复制
在ret的末尾插入v[i]-ASCII为“0”
定义数组ret
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
返回ret
从主要方法中执行以下操作：
ret：=0
从s定义一个数组x=makeVector
当x>1的大小时-
定义大小为1的数组温度
temp[0]：=1
x：=makeVector（addBinary(x,temp)）
从x删除最后一个元素
（增加ret1）
如果x的最后一个元素等于0，则-
除此以外
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string addStrings(vector<int> num1, vector<int> num2){
vector<int> ret;
int carry = 0;
int sum = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int i = 0;
int j = 0;
while (i < num1.size() || j < num2.size()) {
if (i < num1.size() && j < num2.size()) {
sum = carry + (num1[i]) + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
j++;
}
else if (i < num1.size()) {
sum = carry + (num1[i]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
}
else {
sum = carry + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
j++;
}
}
if (carry)
ret.push_back(carry);
i = ret.size() - 1;
string ans = "";
for (; i >= 0; i--)
ans += (ret[i] + '0');
return ans.size() == 0 ? "0" : ans;
}
string addBinary(vector<int>& a, vector<int>& b){
return addStrings(a, b);
}
vector<int> makeVector(string v){
vector<int> ret;
for (int i = 0; i < v.size(); i++)
ret.push_back(v[i] - '0');
return ret;
}
int numSteps(string s){
int ret = 0;
vector<int> x = makeVector(s);
while (x.size() > 1) {
ret++;
if (x.back() == 0) {
x.pop_back();
}
else {
vector<int> temp(1);
temp[0] = 1;
x = makeVector(addBinary(x, temp));
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numSteps("1101"));
}输入值
"1101"
输出结果
6