Ilość liczb z rozważanego przedziału, które w zapisie binarnym posiadają dokładnie jedną jedynkę

Potrzebuję napisać program, który wypisze ile liczb z przedziału od a do b posiada dokładnie jedną jedynkę w systemie dwójkowym. Dodatkowo pytań o to jest z. Jedyne co udało mi się zrobić to wypisać te liczby w systemie dwójkowym. Nie wiem natomiast jak sprawdzić po kolei każdy zapis binarny czy ma on tylko jedną jedynkę. Mam coś takiego:

#include <iostream>

using namespace std;

int z;
int a, b, x;
string wynik;

int main()
{
  cin >> a >> b;
  x = b - a + 1;
  
  while(x < b)
  {
    for(int i; a > 0; i++)
    {
      wynik = (a % 2 ? "1" : "0") + wynik;
      a /= 2;
    }

    a++;
    x++;
    
    cout << wynik << endl;
  }

  return 0;
}

Proponuję inne rozwiązanie.
Zamiast przerabiać na system binarny a potem liczyć czy jest tylko 1 jedynka czy więcej, sprawdź czy log₂(n) jest liczbą całkowitą, możesz to zrobić np. tak:

return ceil(log2(n)) == floor(log2(n));

ceil służy do zaokrąglenia w górę a floor w dół, dzięki czemu porównujemy 2 int,jeżeli będą takie same zwracana jest prawda i oznacza to że liczba ma tylko jedną 1 w systemie binarnym.

Problemem jest gdy n jest równe 0 gdyż wtedy również dostaniemy true. Można więc dodać if który temu zapobiegnie, i tak cała funkcja wygląda następująco

#include <cmath>

bool is_pow2(int n)
{
	if (n == 0)
		return false;
	return ceil(log2(n)) == floor(log2(n));
}

Możesz również zmienić tą pętle while na for co jest czytelniejsze:

// x jest niepotrzebne
int count = 0; // Ilość liczb które spełniają wymagania
for (int i = a; i < b; i++)
{
	if (is_pow2(i))
	{
		count++;
	}
}

cout << "Ilosc liczb: " << count;

Jeśli celujemy w złożoność obliczeniową O(1) to dla całkowitych, dodatnich a, b

floor(log2(b)) - ceil(log2(a)) + 1

#include <iostream>

bool isPowerOfTwo(unsigned val) {
    return val != 0 ? !(val & (val - 1)): false;
}

int main() {
    for(auto i = 0U; i < 10; ++i) {
        std::cout << i << ' ' << std::boolalpha
            << isPowerOfTwo(i) << '\n';
    }
}

Jednak drogą zliczania pomiędzy wartościami bym nie szedł. Złożoność będzie O(n) a można uzyskać O(1) dla tego problemu.

paula18108 napisał(a):

posiada dokładnie jedną jedynkę w systemie dwójkowym.

Tylko potęgi 2 spełniają warunek.
Zaprzęganie do tego liczb zmiennoprzecinkowych to duża przesada.

unsigned int oldestBit(unsigned int x) {
#ifdef __GNUC__
    return x ? (sizeof(x) * CHAR_BIT - __builtin_clz(x)) : 0;
#else
    unsigned int result = 0;
    while (x != 0) {
        ++result;
        x >>= 1;
    }
    return result;
#endif
}

unsigned int countPow2InRange(unsigned int a, unsigned int b) {
    if (a == 0)
         return oldestBit(b);
    return oldestBit(b) - oldestBit(a - 1);
}

https://wandbox.org/permlink/zWcNYawKLOLxj2Gx

atmal napisał(a):

Proponuję inne rozwiązanie.
Zamiast przerabiać na system binarny a potem liczyć czy jest tylko 1 jedynka czy więcej, sprawdź czy log₂(n) jest liczbą całkowitą, możesz to zrobić np. tak:

return ceil(log2(n)) == floor(log2(n));

ceil służy do zaokrąglenia w górę a floor w dół, dzięki czemu porównujemy 2 int,jeżeli będą takie same zwracana jest prawda i oznacza to że liczba ma tylko jedną 1 w systemie binarnym.

Problemem jest gdy n jest równe 0 gdyż wtedy również dostaniemy true. Można więc dodać if który temu zapobiegnie, i tak cała funkcja wygląda następująco

#include <cmath>

bool is_pow2(int n)
{
	if (n == 0)
		return false;
	return ceil(log2(n)) == floor(log2(n));
}

Możesz również zmienić tą pętle while na for co jest czytelniejsze:

// x jest niepotrzebne
int count; // Ilość liczb które spełniają wymagania
for (int i = a; i < b; i++)
{
	if (is_pow2(i))
	{
		count++;
	}
}

cout << "Ilosc liczb: " << count;

reptile333 napisał(a):

Jeśli celujemy w złożoność obliczeniową O(1) to dla całkowitych, dodatnich a, b

floor(log2(b)) - ceil(log2(a)) + 1

Bardzo dziękuję za pomoc. Tylko nie mam zielonego pojęcia dlaczego to nie działa poprawnie:

#include <iostream>
#include <cmath>
using namespace std;


bool is_pow2(int n)
{
   if (n == 0)
       return false;
   return ceil(log2(n)) == floor(log2(n));
}
int z;
int a,b;
int main()
{

   cin>>z;
   for(int j=1; j<=z; j++)
{

 cin >> a >> b;

   int count; // Ilość liczb które spełniają wymagania

     for (int i = a; i < b; i++)
   {
       if (is_pow2(i))
       {
       count++;
       }

   }

cout << "Ilosc liczb: " << count<<endl;
}
   return 0;
}

Wybacz, mój błąd - zapomniałem zainicjalizować zmienną count. Kod powinien wyglądać tak:

int count = 0; // Ilość liczb które spełniają wymagania

for (int i = a; i < b; i++)
{
	if (is_pow2(i))
	{
		count++;
	}
}