【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字

class Solution {
public:
  long long findMaximumNumber(long long k, int x) {
    long long left = 0, r = 5e17;
    while (r - left > 1)
    {
      const auto mid = left + (r - left) / 2;
      if (Cnt(mid, k,x) <= k)
      {
        left = mid;
      }
      else
      {
        r = mid;
      }
    }
    return left;
  }
  long long Cnt(long long mid,int k,int x )
  {
    long long llCnt = 0;
    for (int ii = x; ii <= 60; ii += x)
    {
      const long long tmp = 1LL << ii;//周期
      const long long cur1 = (mid + 1) / tmp * (tmp / 2); 
      const long long cur2 = max(0LL, (mid + 1) % tmp - tmp / 2);
      if (LLONG_MAX - llCnt < cur1)
      {
        return k + 1;
      }
      llCnt += cur1;
      if (LLONG_MAX - llCnt < cur2)
      {
        return k + 1;
      }
      llCnt += cur2;
    }
    return llCnt;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  long long k;
  int x;
  {
    Solution sln;
    k = 19, x = 6;
    auto res = sln.findMaximumNumber(k, x);
    Assert(50LL, res);
  }
  {
    Solution sln;
    k = 9, x = 1;
    auto res = sln.findMaximumNumber(k, x);
    Assert(6LL, res);
  }
  {
    Solution sln;
    k = 7, x = 2;
    auto res = sln.findMaximumNumber(k, x);
    Assert(9LL, res);
  }
  {
    Solution sln;
    k = 343883588590415, x = 1;
    auto res = sln.findMaximumNumber(k, x);
    //Assert(9LL, res);
  } 
}