C++のb-baseで数値Nが1で始まるかどうかを確認します

数Nと底bがあります。このプログラムでは、基数bの1から始まるかどうかを確認する必要があります。番号6が与えられたと仮定します。バイナリではこれは110なので、1から始まり、ベース4でも12 ₄になります。 。ここでも1から始まります。

ご存知のように、基数bで数値Nが表される場合、bはm+1ビットシーケンスbmbm-1…b0に変換されます。これは、b _mを意味します b ^m + b _m-1 * b ^m-1 +…+b ₀ * b ⁰ =N。最大数は2*b ^m になります。 –1.Nはb ^m にあります ≤N≤2*b ^m – 1.ここで、mが$ \ lfloor \ log_2 m \; \ rfloor $を超えることはできないことに注意してください。これは、基数2で任意の数値を表すと、0と1のみのシーケンスに変換されるためです。このシーケンスの長さは常に他のどの基数表現よりも長く、その長さは$ \ lfloor \ log_2 m \; \ rfloor +1$に等しくなります。したがって、与えられた数Nが基数bの1で始まるかどうかを確認するには、m=1からm=$ \ lfloor \ log_2 m \; \ rfloor $までトラバースし、mの値がNであるかどうかを確認します。範囲b ^m ≤N≤2*b ^m – 1かどうかに応じて、Trueまたはfalseを返します。

例

#include <iostream>
#include <cmath>
using namespace std;
bool isStartWithOne(int number, int base) {
   int m = log2(number);
   for (int i = 1; i <= m; i++) {
      if (number >= pow(base, i) && number <= 2 * pow(base, i) - 1) //if number is in the given range
   return true;
   }
   return false;
}
int main() {
int num = 19, base = 16;
   if(isStartWithOne(num, base)){
      cout << "Can be represented";
   }else{
      cout << "Can not be represented";
   }
}

出力

Can be represented