c++ - 将二进制表示形式的数字减少到 1 的步骤数

Question

给定一个整数作为字符串 s 的二进制表示，根据以下规则返回将其减少到 1 的步数:

如果当前数是偶数，则必须除以 2。

如果当前数字是奇数，则必须将其加1。

保证所有测试用例总能达到一个。

第1步)13是奇数，加1得到14。

第2步)14是偶数，除以2得7。

第三步)7是奇数，加1得8。

第4步)8是偶数，除以2得4。

第5步)4是偶数，除以2得2。

第6步)2为偶数，除以2得1。

我的输入 = 1111011110000011100000110001011011110010111001010111110001

预期输出 = 85

我的输出 = 81

对于上面的输入，输出应该是85。但我的输出显示81。对于其他测试用例它似乎给出了正确的答案。我一直在尝试所有可能的调试，但我被卡住了。

#include <iostream>
#include <string.h>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s = 
     "1111011110000011100000110001011011110010111001010111110001";
  long int count = 0, size;
  unsigned long long int dec = 0;
  size = s.size();
  // cout << s[size - 1] << endl;
  for (int i = 0; i < size; i++)
  {
   // cout << pow(2, size - i - 1) << endl;
    if (s[i] == '0')
        continue;
    // cout<<int(s[i])-48<<endl;
    dec += (int(s[i]) - 48) * pow(2, size - 1 - i);
  }
  // cout << dec << endl;
  //  dec = 278675673186014705;

  while (dec != 1)
  {

    if (dec % 2 == 0)
        dec /= 2;
    else
        dec += 1;
    count += 1;
  }

  cout << count;
  return 0;

Answer 1

这一行:

pow(2, size - 1 - i)

可能面临精度错误 pow takes and returns doubles .

幸运的是，对于不会溢出 unsigned long long 的以 2 为底的幂，我们可以简单地使用位移位(相当于 pow(2, x) ).

将该行替换为:

1LL<<(size - 1 - i)

所以它看起来应该是这样的:

dec += (int(s[i]) - 48) * 1ULL<<(size - 1 - i);

我们将得到 85 的正确输出。

注意:如@RSahu所述，您可以删除(int(s[i]) - 48)，如int(s[i]) == ' 0' 已经在上面的 if 语句中。只需将行更改为:

dec += 1ULL<<(size - 1 - i);